পাইথনে যোগফল k-র দ্বারা বিভাজ্য করতে মুছে ফেলার ক্ষুদ্রতম সাবলিস্টের দৈর্ঘ্য বের করার প্রোগ্রাম

একটি ধনাত্মক সংখ্যার তালিকা (nums) এবং একটি ধনাত্মক সংখ্যা k দেওয়া আছে। nums-র একটি সাবলিস্ট (খালিও হতে পারে) মুছে ফেলা যাবে যাতে বাকি উপাদানগুলোর যোগফল k-র দ্বারা বিভাজ্য হয়। পুরো তালিকা মুছে ফেলা যাবে না। এমন সাবলিস্টের ক্ষুদ্রতম দৈর্ঘ্য বের করতে হবে। না থাকলে -1 রিটার্ন করুন।

সমস্যা উদাহরণ

ইনপুট: nums = [5, 8, 6, 3], k = 8 আউটপুট: 1


ব্যাখ্যা: মোট যোগফল = ২২। [৬] (দৈর্ঘ্য ১) মুছে দিলে যোগফল = ১৬, যা ৮-র দ্বারা বিভাজ্য।

সমাধানের পদ্ধতি (প্রিফিক্স সাম + হ্যাশ ম্যাপ)

rem = (sum(nums) + k) % k (মোট যোগফলের রিমেইনডার)
যদি rem == 0 হলে ০ রিটার্ন করুন (কিছু মুছে ফেলার দরকার নেই)
presum = 0, mp = {0: -1} (রিমেইনডার → সর্বশেষ ইনডেক্স)
res = n
প্রতিটি i (০ থেকে n-১) এর জন্য:

presum += nums[i]
m = (presum + k) % k
mp[m] = i
যদি (m - rem + k) % k mp-তে থাকে তবে res = min(res, i - mp[(m - rem + k) % k])


res if res != n else -1 রিটার্ন করুন


পাইথন কোড
def solve(nums, k):
    rem = (sum(nums) + k) % k
    if rem == 0:
        return 0
    n, presum = len(nums), 0
    mp = {0: -1}
    res = n
    for i in range(n):
        presum += nums[i]
        m = (presum + k) % k
        mp[m] = i
        if (m - rem + k) % k in mp:
            res = min(res, i - mp[(m - rem + k) % k])
    return res if res != n else -1

nums = [5, 8, 6, 3]
k = 8
print(solve(nums, k))  # আউটপুট: 1

টেস্ট কেস
ইনপুট: [5, 8, 6, 3], 8

আউটপুট: 1