Python में ऐरे को पूरक बनाने के लिए न्यूनतम चाल खोजने का प्रोग्राम

मान लीजिए हमारे पास सम लंबाई का एक ऐरे nums और एक मान limit है। एक चाल में, हम nums से किसी भी मान को 1 और limit के बीच किसी अन्य मान से बदल सकते हैं। ऐरे को पूरक कहा जाता है यदि सभी इंडेक्स i के लिए, nums[i] + nums[n-1-i] समान संख्या के बराबर हो। तो हमें nums को पूरक बनाने के लिए आवश्यक न्यूनतम चालों की संख्या ढूंढनी है।

उदाहरण के लिए, यदि इनपुट है nums = [1,4,2,3], limit = 4, तो आउटपुट 1 होगा क्योंकि एक चाल में हम इंडेक्स 1 पर तत्व को 2 बना सकते हैं, तो ऐरे होगा [1,2,2,3], फिर nums[0] + nums[3] = 4, nums[1] + nums[2] = 4, nums[2] + nums[1] = 4, nums[3] + nums[0] = 4।

समाधान के चरण

1. n := len(nums)
2. mid := n // 2
3. zero_moves := इंटीजर टाइप मान का खाली मैप
4. start := आकार (2 * limit + 1) की ऐरे, और 0 से भरी
5. end := आकार (2 * limit + 1) की ऐरे, और 0 से भरी
6. res := infinity
7. i को 0 से mid-1 तक:
   • x := nums[i]
   • y := nums[n-1-i]
   • zero_moves[x+y] += 1
   • start[min(x,y)+1] += 1
   • end[max(x,y)+limit] += 1
8. intervals := 0
9. target को 2 से limit*2 तक:
   • intervals += start[target]
   • cost := 2*(mid-intervals) + intervals - zero_moves[target]
   • res := min(res, cost)
   • intervals -= end[target]
10. res वापस करें

उदाहरण

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

from collections import defaultdict

def solve(nums, limit):
    n = len(nums)
    mid = n // 2
    zero_moves = defaultdict(int)
    start = [0] * (2 * limit + 1)
    end = [0] * (2 * limit + 1)
    res = float('inf')
    for i in range(mid):
        x = nums[i]
        y = nums[n - 1 - i]
        zero_moves[x + y] += 1
        start[min(x, y) + 1] += 1
        end[max(x, y) + limit] += 1
    intervals = 0
    for target in range(2, limit * 2 + 1):
        intervals += start[target]
        cost = 2 * (mid - intervals) + intervals - zero_moves[target]
        res = min(res, cost)
        intervals -= end[target]
    return res

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

इनपुट

[1,4,2,3], 4

आउटपुट

1