एक संख्याओं की सूची nums दी गई है जिसकी लंबाई सम है। एक ऑपरेशन में हम सूची के किसी भी संख्या को 1 से अधिकतम संख्या तक की रेंज में किसी भी मान से अपडेट कर सकते हैं। हमें न्यूनतम ऑपरेशन खोजने हैं ताकि प्रत्येक i के लिए, nums[i] + nums[n-1-i] का योग समान हो।
उदाहरण
इनपुट: nums = [8,6,2,5,9,2]
आउटपुट: 2
व्याख्या: यदि हम nums[2] पर पहले 2 को 5 में बदलें, और nums[4] पर 9 को 4 में बदलें, तो तत्व बन जाएंगे [8,6,5,5,4,2], तब प्रत्येक i के लिए nums[i] + nums[n-1-i] होगा (8+2) = (6+4) = (5+5) = 10।
एल्गोरिदम
N:= nums का आकारmx:= nums का अधिकतम मानevents:= एक नई सूचीidx:= 0- जब
idx < N // 2हो:a := nums[idx]b := nums[N - idx - 1]eventsमें जोड़ें:(min(a + 1, b + 1), 1)eventsमें जोड़ें:(a + b, 1)eventsमें जोड़ें:(a + b + 1, -1)eventsमें जोड़ें:(max(a + mx, b + mx) + 1, -1)idx := idx + 1
eventsसूची को सॉर्ट करेंcurrent := 0,mx_same := 0- प्रत्येक
(event, delta)जोड़ी के लिएeventsमें:current := current + deltamx_same := max(current, mx_same)
N - mx_sameलौटाएं
Python कार्यान्वयन
def solve(nums):
N = len(nums)
mx = max(nums)
events = []
idx = 0
while idx < N // 2:
a = nums[idx]
b = nums[N - idx - 1]
events.append((min(a + 1, b + 1), 1))
events.append((a + b, 1))
events.append((a + b + 1, -1))
events.append((max(a + mx, b + mx) + 1, -1))
idx += 1
events.sort()
current = 0
mx_same = 0
for event, delta in events:
current += delta
mx_same = max(current, mx_same)
return N - mx_same
nums = [8, 6, 2, 5, 9, 2]
print(solve(nums)) # आउटपुट: 2
इनपुट/आउटपुट
Input: [6, 8, 5, 2, 3]
Output: 2