ধরুন আমাদের কাছে ধনাত্মক মানের একটি তালিকা আছে, যাকে nums বলা হয় এবং একটি ধনাত্মক সংখ্যা k আছে। আমাদের সংক্ষিপ্ততম সাবলিস্টের দৈর্ঘ্য খুঁজে বের করতে হবে (খালি হতে পারে) যা আমরা সংখ্যা থেকে মুছে ফেলতে পারি, যেমন অবশিষ্ট উপাদানগুলির যোগফল k দ্বারা বিভাজ্য। কিন্তু আমরা সম্পূর্ণ তালিকা মুছে ফেলতে পারি না। যদি মুছে ফেলার মতো কোনো সাবলিস্ট না থাকে, তাহলে -1 রিটার্ন করুন।
সুতরাং, ইনপুট যদি nums =[5,8,6,3] k =8 এর মত হয়, তাহলে আউটপুট হবে 1, কারণ [5,8,6,3] এর উপাদানগুলির বর্তমান যোগফল হল 22। যদি আমরা দৈর্ঘ্য 1 এর সাবলিস্ট [6] সরান, তারপর যোগফল 16, যা 8 দ্বারা বিভাজ্য।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- rem :=(সংখ্যা + k-এ উপস্থিত সমস্ত উপাদানের যোগফল) mod k
- যদি rem 0 এর মত হয়, তাহলে
- রিটার্ন 0
- n :=সংখ্যার আকার
- presum :=0
- mp :=একটি অভিধান, প্রাথমিকভাবে 0 কী এর জন্য -1 সংরক্ষণ করুন
- res :=n
- আমি 0 থেকে n - 1 রেঞ্জের জন্য, কর
- presum :=presum + nums[i]
- m :=(presum + k) mod k
- mp[m] :=i
- যদি (m - rem + k) mod k থাকে mp-এ, তাহলে
- res :=ন্যূনতম রেস এবং (i - mp[(m - rem + k) mod k])
- res ফেরত দিন যদি res একই না হয় n অন্যথায় -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)) ইনপুট
[5,8,6,3], 8
আউটপুট
1
