পাইথনে অ্যারের দুপাশ থেকে এলিমেন্ট মুছে X শূন্য করার ন্যূনতম অপারেশন বের করার প্রোগ্রাম

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

যেমন, ইনপুট হলে nums = [4,2,9,1,4,2,3], x = 9, তবে আউটপুট হবে 3 কারণ: প্রথমে বামে ৪ মুছে x=5, পরে ডানে ৩ মুছে x=2, আবার বামে বা ডানে ২ মুছে x=0।

সমাধানের ধাপসমূহ

n := len(nums)
leftMap := {0: -1}
left := 0
i = 0 থেকে n-1 পর্যন্ত: left += nums[i], যদি left not in leftMap হয় leftMap[left] = i
right := 0, ans := n+1
i = n থেকে 0 পর্যন্ত (কমাতে):
- যদি i < n হয়, তবে right += nums[i]
- left := x - right
- যদি left in leftMap হয়, তবে ans = min(ans, leftMap[left] + 1 + n - i)
যদি ans == n+1 হয়, তবে -1 রিটার্ন করুন।
ans রিটার্ন করুন।

উদাহরণ

নিচের ইমপ্লিমেন্টেশনটি দেখুন:

def solve(nums, x):
    n = len(nums)
    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