পাইথনে সাব-অ্যারে মুছে সম P দিয়ে ডিভISIBLE করার প্রোগ্রাম

মান লিজিয়ে একটি অ্যারে আছে nums এবং আরেকটি মান p। আমরা সবচেয়ে ছোট সাব-অ্যারে (পুরো অ্যারে না) মুছে দেব যাতে বাকি এলিমেন্টগুলোর সম p দিয়ে ডিভISIBLE হয়। মুছে দেওয়া সাব-অ্যারের ন্যূনতম দৈর্ঘ্য বের করতে হবে, না থাকলে -1 রিটার্ন করুন।

যেমন, ইনপুট হলে nums = [8,2,6,5,3], p = 7, তবে আউটপুট হবে 1 কারণ ৩ মুছে দিলে মোট সম 21 হবে যা ৭ দিয়ে ডিভISIBLE।

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

ans := infinity
s := sum(nums) % p
d := {0: -1}
cum := 0
যদি s == 0 হয়, তবে 0 রিটার্ন করুন।
i = 0 থেকে len(nums)-1 পর্যন্ত:
- cum += nums[i]
- r := cum % p
- যদি (r-s)%p in d হয়, তবে ans = min(ans, i - d[(r-s)%p])
- d[r] = i
ans if ans < len(nums) else -1 রিটার্ন করুন।

উদাহরণ

নিচের ইমপ্লিমেন্টেশনটি দেখুন:

def solve(nums, p):
    ans = float("inf")
    s = sum(nums) % p
    d = {0: -1}
    cum = 0
    if s == 0:
        return 0
    for i in range(len(nums)):
        cum += nums[i]
        r = cum % p
        if (r - s) % p in d:
            ans = min(ans, i - d[(r - s) % p])
        d[r] = i
    return ans if ans < len(nums) else -1

nums = [8,2,6,5,3]
p = 7
print(solve(nums, p))

ইনপুট

[8,2,6,5,3], 7