পাইথনে সমান যোগফলের সাথে k সাবয়ারেতে পার্টিশন করা সম্ভব কিনা তা পরীক্ষা করুন

ধরুন আমাদের কাছে সংখ্যার একটি অ্যারে আছে যাকে nums বলা হয় এবং এর আরেকটি মান K আছে। আমাদের পরীক্ষা করতে হবে যে আমরা অ্যারের সংখ্যাগুলিকে K সংলগ্ন সাব্যারেতে বিভাজন করতে পারব কি না যাতে প্রতিটি সাবয়ারের উপাদানের যোগফল সমান হয়।

সুতরাং, যদি ইনপুটটি nums =[2, 5, 3, 4, 7] k =3 এর মত হয়, তাহলে আউটপুটটি True হবে কারণ আমরা [(2, 5), (3, 4), এর মতো তিনটি পার্টিশন তৈরি করতে পারি। (7)] সবার সমান যোগফল 7।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• n :=সংখ্যার আকার
• cumul_sum :=সংখ্যায় সমস্ত উপাদানের ক্রমবর্ধমান যোগফল
• মোট_সমষ্টি :=cumul_sum[n - 1]
• যদি মোট_সমষ্টি k দ্বারা বিভাজ্য না হয়, তাহলে
  • মিথ্যে ফেরত দিন
• গণনা :=0, অবস্থান :=-1
• আমি 0 থেকে n - 1 রেঞ্জের জন্য, কর
  • যদি pos -1 এর মত হয়, তাহলে
    • উপ :=0
  • অন্যথায়,
    • উপ :=cumul_sum[pos]
  • যদি cumul_sum[i] - সাব হয় (total_sum / K), তাহলে
    • pos :=i
    • গণনা :=গণনা + 1
  • অন্যথায় যখন cumul_sum[i] - cumul_sum[pos]> (total_sum / K), তারপর
    • লুপ থেকে বেরিয়ে আসুন
• সত্য প্রত্যাবর্তন করুন যখন গণনা K এর সমান হয় অন্যথায় মিথ্যা

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

def solve(nums, k):
   n = len(nums)
   cumul_sum = [0 for i in range(n)]
   cumul_sum[0] = nums[0]
   for i in range(1, n):
      cumul_sum[i] = cumul_sum[i - 1] + nums[i]
   total_sum = cumul_sum[n - 1]
   if total_sum % k != 0:
      return False
   count = 0
   pos = -1
   for i in range(n):
      if pos == -1:
         sub = 0
      else:
         sub = cumul_sum[pos]
      if cumul_sum[i] - sub == total_sum / k:
         pos = i
         count += 1
      elif cumul_sum[i] - cumul_sum[pos] > total_sum / k:
         break
   return count == k
nums = [2, 5, 3, 4, 7]
k = 3
print(solve(nums, k))

ইনপুট

[2, 5, 3, 4, 7], 3

আউটপুট

True