Python में 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]।

समाधान के चरण

1. n := len(nums)
2. leftMap := {} (नया मैप)
3. leftMap[0] := -1
4. left := 0
5. i को 0 से n-1 तक:
   • left := left + nums[i]
   • यदि left leftMap में नहीं है:
     • leftMap[left] := i
6. right := 0
7. ans := n + 1
8. i को n से 0 तक घटाते हुए:
   • यदि i < n:
     • right := right + nums[i]
   • left := x - right
   • यदि left leftMap में मौजूद है:
     • ans := min(ans, leftMap[left] + 1 + n - i)
9. यदि ans == n + 1:
   • -1 वापस करें
10. ans वापस करें

उदाहरण

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

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