ধরুন আমাদের একটি অ্যারের সংখ্যা এবং আরেকটি মান p আছে, আমরা ক্ষুদ্রতম সাব্যারে (পুরো অ্যারে নয়) সরিয়ে ফেলি যাতে অবশিষ্ট মানের যোগফল p দ্বারা বিভাজ্য হয়। আমাদেরকে অপসারণ করতে হবে এমন ক্ষুদ্রতম সাবয়ারের দৈর্ঘ্য খুঁজে বের করতে হবে, যদি এমন কোন সাবয়ারে না থাকে তাহলে -1 রিটার্ন করুন।
সুতরাং, ইনপুট যদি nums =[8,2,6,5,3] p =7 এর মত হয়, তাহলে আউটপুট হবে 1 কারণ যদি আমরা 3টি সরিয়ে দেই, তাহলে মোট যোগফল হবে 21 এবং সেটি 7 দ্বারা বিভাজ্য।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- উত্তর :=অসীম
- s :=(সংখ্যায় সমস্ত উপাদানের যোগফল) mod p
- d :=একটি মানচিত্রে কী-মান জোড়া রয়েছে {0:-1}
- কাম :=0
- যদি s 0 এর সমান হয়, তাহলে
- রিটার্ন 0
- আমি 0 থেকে সংখ্যার আকারের মধ্যে,
- করুন
- কাম :=সহ + সংখ্যা[i]
- r :=কাম মোড পি
- যদি d-এ (r-s)mod p থাকে, তাহলে
- উত্তর :=সর্বনিম্ন উত্তর এবং i - d[(r-s) mod p]
- d[r] :=i
- উত্তর দিন যদি উত্তর হয় <সংখ্যার আকার অন্যথায় -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
আউটপুট
1
