পাইথনে X-কে শূন্য থেকে কমাতে ন্যূনতম অপারেশন খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের একটি অ্যারে আছে যার নাম nums এবং আরেকটি মান x। একটি অপারেশনে, আমরা অ্যারে থেকে বাম বা ডানদিকের উপাদানটি মুছে ফেলতে পারি এবং x থেকে মান বিয়োগ করতে পারি। x কে ঠিক 0 এ কমাতে আমাদের ন্যূনতম সংখ্যক ক্রিয়াকলাপ খুঁজে বের করতে হবে। যদি এটি সম্ভব না হয় তবে -1 ফেরত দিন।

সুতরাং, যদি ইনপুটটি nums =[4,2,9,1,4,2,3] x =9 এর মত হয়, তাহলে আউটপুট হবে 3 কারণ প্রথমে আমাদের বাম অধিকাংশ উপাদান 4 মুছে ফেলতে হবে, তাই অ্যারে হবে [2,9,1,4,2,3] এবং x হবে 5, তারপর ডানদিকের সবচেয়ে উপাদান 3টি সরিয়ে ফেলুন, তাই অ্যারে হবে [2,9,1,4,2], এবং x =2, তারপর আবার হয় x =0 করতে বাম থেকে বাম বা ডান থেকে, এবং অ্যারে হবে [2,9,1,4] বা [9,1,4,2]।

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

• n :=সংখ্যার আকার
• leftMap :=একটি নতুন মানচিত্র
• leftMap[0] :=-1
• বামে :=0
• আমি 0 থেকে n - 1 রেঞ্জের জন্য, কর
  • left :=left + nums[i]
  • লেফট ম্যাপে যদি লেফট না থাকে, তাহলে
    • leftMap[left] :=i
• ডান :=0
• উত্তর :=n + 1
• n থেকে 0 রেঞ্জের i এর জন্য, 1 কমিয়ে
  করুন
  • যদি i
  • right :=right + nums[i]
• বামে :=x - ডান
• লেফট ম্যাপে যদি লেফট থাকে, তাহলে
  • উত্তর :=সর্বনিম্ন উত্তর এবং বামম্যাপ[বাম] + 1 + n-i

উদাহরণ

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

def solve(nums, x):
   n = len(nums)

   leftMap = dict()
   leftMap[0] = -1
   left = 0
   for i in range(n):
      left += nums[i]
      if left not in leftMap:
         leftMap[left] = i

   right = 0
   ans = n + 1
   for i in range(n, -1, -1):
      if i < n:
         right += nums[i]
      left = x - right
      if left in leftMap:
         ans = min(ans, leftMap[left] + 1 + n - i)
   if ans == n + 1:
      return -1
   return ans

nums = [4,2,9,1,4,2,3]
x = 9
print(solve(nums, x))

ইনপুট

[4,2,9,1,4,2,3], 9

আউটপুট

3