পাইথনে k দ্বারা বিভাজ্য যোগফল वाले কনসিকিউটিভ সাবসিকোয়েন্সের সংখ্যা খুঁজে বের করা

একটি অ্যারে nums এবং একটি মান k দেওয়া আছে। আমাদের এমন কনসিকিউটিভ সাবসিকোয়েন্সের সংখ্যা বের করতে হবে যাদের যোগফল k দ্বারা বিভাজ্য।

উদাহরণ

ইনপুট: k = 3, nums = [1, 2, 3, 4, 1]

আউটপুট: 4

কারণ সাবসিকোয়েন্সগুলো হল: [3], [1, 2], [1, 2, 3], [2, 3, 4]

সমাধান পদ্ধতি

1. x নামে সাইজ k একটি অ্যারে তৈরি করুন এবং ০ দিয়ে ফিল করুন।
2. x[0] := 1 সেট করুন।
3. r := 0, s := 0 ইনিশিয়ালাইজ করুন।
4. nums-এর প্রতিটি elem এর জন্য:
   • s := (s + elem) % k
   • r := r + x[s]
   • x[s] := x[s] + 1
5. r রিটার্ন করুন।

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

def solve(k, nums):
    x = [0] * k
    x[0] = 1
    r = s = 0
    for elem in nums:
        s = (s + elem) % k
        r += x[s]
        x[s] += 1
    return r

# টেস্ট
k = 3
nums = [1, 2, 3, 4, 1]
print(solve(k, nums))  # আউটপুট: 4

ইনপুট

3, [1,2,3,4,1]

আউটপুট

4