পাইথনে অ্যারে কমপ্লিমেন্টারি করার ন্যূনতম মুভ বের করার প্রোগ্রাম

মান লিজিয়ে একটি অ্যারে আছে nums ইভেন দৈর্ঘ্যের এবং আরেকটি মান limit। এক মুভে আমরা nums-এর যেকোনো মান কে ১ থেকে limit পর্যন্ত যেকোনো মান দিয়ে রিপ্লেস করতে পারি। অ্যারেটি complementary বলা হয় যদি সব i এর জন্য nums[i] + nums[n-1-i] একই সংখ্যা হয়। ন্যূনতম কত মুভ লাগবে nums-কে কমপ্লিমেন্টারি করতে সেটি বের করতে হবে।

যেমন, ইনপুট হলে nums = [1,4,2,3], limit = 4, তবে আউটপুট হবে 1 কারণ এক মুভে ইন্ডেক্স ১-কে ২ করলে অ্যারে হবে [1,2,2,3], তাহলে nums[0]+nums[3]=4, nums[1]+nums[2]=4, nums[2]+nums[1]=4, nums[3]+nums[0]=4।

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

• n := len(nums)

• mid := n // 2

• zero_moves := ডিফল্টডিক্ট(int)

• start := [0] * (2*limit + 1)

• end := [0] * (2*limit + 1)

• res := infinity

• 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

• intervals := 0

• target = 2 থেকে 2*limit পর্যন্ত:

  • intervals += start[target]

  • cost := 2*(mid - intervals) + intervals - zero_moves[target]

  • res = min(res, cost)

  • intervals -= end[target]

• 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