একটি সমান দৈর্ঘ্যের সংখ্যা তালিকা (nums) দেওয়া আছে। একটি অপারেশনে তালিকার যেকোনো একটি সংখ্যাকে ১ থেকে তালিকার সর্বোচ্চ মান পর্যন্ত যেকোনো মানের সাথে আপডেট করা যাবে। লক্ষ্য হলো কমপক্ষে কতগুলো অপারেশন দরকার যাতে প্রতিটি i-এর জন্য nums[i] + nums[n-1-i] একই মান হয়।
সমস্যা উদাহরণ
ইনপুট: nums = [8, 6, 2, 5, 9, 2]
আউটপুট: 2
ব্যাখ্যা: nums[2] (২) কে ৫ এবং nums[4] (৯) কে ৪ করে দিলে তালিকা হয় [8, 6, 5, 5, 4, 2]। এখন প্রতিটি জোড়ার যোগফল: (৮+২) = (৬+৪) = (৫+৫) = ১০।
সমাধানের পদ্ধতি
N := numsএর আকারmx := numsএর সর্বোচ্চ মানevents := []খালি তালিকা- প্রতিটি জোড়া (i, N-i-1) এর জন্য ইভেন্ট পয়েন্ট গণনা করুন:
(min(a+1, b+1), 1)(a+b, 1)(a+b+1, -1)(max(a+mx, b+mx)+1, -1)
- ইভেন্টগুলো সাজান
- সইপ লাইন অ্যালগরিদম ব্যবহার করে সর্বোচ্চ ওভারল্যাপিং ইভেন্ট বের করুন (
mx_same) - উত্তর:
N - mx_same
পাইথন কোড
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টেস্ট কেস
ইনপুট: [6, 8, 5, 2, 3]
আউটপুট: 2
