পাইথনে কোয়েরি দিয়ে অ্যারিথমেটিক সিকোয়েন্স চেক করা

একটি নম্বর লিস্ট এবং কোয়েরি লিস্ট দেওয়া আছে। প্রতিটি কোয়েরি [i, j] বুঝায় সাবলিস্ট nums[i:j+1] অ্যারিথমেটিক সিকোয়েন্স কিনা। সত্য কোয়েরির সংখ্যা বের করুন।

ইনপুট উদাহরণ

nums = [2, 4, 6, 8, 7, 6, 5, 2]
queries = [[3,4], [0,3], [2,4]]

আউটপুট: 2 ([0,3] এবং [3,4] সত্য)

অ্যালগরিদম

1. ডিফারেন্স অ্যারে diff[i] = nums[i+1] - nums[i] বানান।
2. RLE (Run Length Encoding) দিয়ে কনsekutিভ সমান ডিফারেন্সের লেংথ স্টোর করুন rle[i]-এ।
3. কোয়েরি [i,j] এর জন্য: rle[j-1] >= (j-i) হলে অ্যারিথমেটিক।

পাইথন কোড

def solve(nums, queries):
    if not nums:
        return 0
    n = len(nums)
    diff = [nums[i+1] - nums[i] for i in range(n-1)]
    rle = [0] * (n-1)
    for i in range(n-1):
        if i > 0 and diff[i] == diff[i-1]:
            rle[i] = rle[i-1] + 1
        else:
            rle[i] = 1
    ans = 0
    for i, j in queries:
        if i == j:
            ans += 1
        else:
            ans += rle[j-1] >= (j - i)
    return ans

# টেস্ট
print(solve([2,4,6,8,7,6,5,2], [[3,4],[0,3],[2,4]]))  # 2

ব্যাখ্যা

প্রিকম্পিউটেশন O(n), প্রতিটি কোয়েরি O(1)। মোট O(n + q)।