পাইথনে লিস্ট থেকে অ্যারিথমেটিক সাবসিকোয়েন্সের সংখ্যা বের করার প্রোগ্রাম

ধরা যাক nums নামক একটি সংখ্যার লিস্ট দেওয়া আছে। আমাদের দৈর্ঘ্য ≥ ৩ এমন অ্যারিথমেটিক সাবসিকোয়েন্সের সংখ্যা বের করতে হবে। অ্যারিথমেটিক সিকোয়েন্স বলতে সেটির প্রতিটি পরপর দুটি সংখ্যার পার্থক্য একই থাকে এমন সিকোয়েন্সকে বোঝায়।

উদাহরণ

ইনপুট: nums = [6, 12, 13, 8, 10, 14]

আউটপুট: 3

ব্যাখ্যা: সাবসিকোয়েন্সগুলো: [6, 8, 10], [6, 10, 14], [12, 13, 14]

সমাধানের ধাপসমূহ

1. dp := একটি নতুন ম্যাপ (কি: (index, diff), মান: গণনা)
2. n := len(nums)
3. res := 0
4. i = 0 থেকে n-1 পর্যন্ত:
   • j = 0 থেকে i-1 পর্যন্ত:
     • diff := nums[i] - nums[j]
     • prev := dp.get((i, diff), 0)
     • prevprev := dp.get((j, diff), 0)
     • dp[(i, diff)] = prev + prevprev + 1
     • res += prevprev
5. res ফেরত দিন

পাইথন ইমপ্লিমেন্টেশন

class Solution:
    def solve(self, nums):
        dp = {}
        n = len(nums)
        res = 0
        for i in range(n):
            for j in range(i):
                diff = nums[i] - nums[j]
                prev = dp.get((i, diff), 0)
                prevprev = dp.get((j, diff), 0)
                dp[(i, diff)] = prev + prevprev + 1
                res += prevprev
        return res

ob = Solution()
nums = [6, 12, 13, 8, 10, 14]
print(ob.solve(nums))

ইনপুট

[6, 12, 13, 8, 10, 14]

আউটপুট

3