মনে করুন nums নামে একটি অ্যারে এবং goal নামে আরেকটি মান আছে। আমরা nums-এর একটি সাবসিকোয়েন্স সিলেক্ট করতে চাই যাতে এর এলিমেন্টগুলোর সমষ্টি goal-এর সবচেয়ে নিকটে থাকে। অর্থাৎ, যদি সাবসিকোয়েন্সের এলিমেন্টগুলোর সমষ্টি s হয়, তবে আমরা |s - goal|-এর আবসোলিউট ডিফারেন্স ন্যূনতম করতে চাই।
সুতরাং আমাদের |s - goal|-এর ন্যূনতম সম্ভাব্য মান বের করতে হবে। সুতরাং, যদি ইনপুট হয় nums = [8,-8,16,-1], goal = -3, তবে আউটপুট হবে 2 কারণ সাবসিকোয়েন্স [8,-8,-1] সিলেক্ট করলে এর সমষ্টি -1। আবসোলিউট ডিফারেন্স |-1 - (-3)| = abs(2) = 2, যা ন্যূনতম।
এটি সমাধান করতে আমরা নিচের ধাপগুলো অনুসরণ করব −
n := nums-এর আকার
numsকে |x|-এর নেগেটিভ ভ্যালু অনুযায়ী সর্ট করুন
neg := n+1 আকারের একটি অ্যারে 0 দিয়ে পূরণ
pos := n+1 আকারের একটি অ্যারে 0 দিয়ে পূরণ
i = n-1 থেকে 0 পর্যন্ত, ১ কমানো করে, করুন
যদি nums[i] < 0 হয়, তবে
neg[i] := neg[i+1] + nums[i]
pos[i] := pos[i+1]
অন্যথায়,
pos[i] := pos[i+1] + nums[i]
neg[i] := neg[i+1]
ans := |goal|
s := একটি নতুন সেট এবং 0 ইনসার্ট করুন
একটি check() ফাংশন ডিফাইন করুন। এটি a, b নেবে
যদি b < goal - ans বা goal + ans < a হয়, তবে
False রিটার্ন করুন
True রিটার্ন করুন
মেইন মেথড থেকে, নিচের কাজ করুন
i = 0 থেকে n-1 পর্যন্ত জন্য, করুন
sl := s-এ সব x যার জন্য check(x+neg[i], x+pos[i]) true]
যদি sl-এর আকার 0 হয়, তবে
লুপ থেকে বের হোন
s := sl থেকে একটি নতুন সেট
sl-এ প্রতিটি x-এর জন্য, করুন
y := x + nums[i]
যদি |y - goal| < ans হয়, তবে
ans := |y - goal|
যদি ans == 0 হয়, তবে
0 রিটার্ন করুন
s-এ y ইনসার্ট করুন
ans রিটার্ন করুন
উদাহরণ
বेहतर বোঝার জন্য নিচের ইমপ্লিমেন্টেশন দেখুন
from collections import Counter
def solve(nums, goal):
n = len(nums)
nums.sort(key=lambda x: -abs(x))
neg = [0 for _ in range(n+1)]
pos = [0 for _ in range(n+1)]
for i in range(n-1, -1, -1):
if nums[i] < 0:
neg[i] = neg[i+1] + nums[i]
pos[i] = pos[i+1]
else:
pos[i] = pos[i+1] + nums[i]
neg[i] = neg[i+1]
ans = abs(goal)
s = set([0])
def check(a, b):
if b < goal - ans or goal + ans < a:
return False
return True
for i in range(n):
sl = [x for x in s if check(x+neg[i], x+pos[i])]
if len(sl) == 0:
break
s = set(sl)
for x in sl:
y = x + nums[i]
if abs(y - goal) < ans:
ans = abs(y - goal)
if ans == 0:
return 0
s.add(y)
return ans
nums = [8,-8,16,-1]
goal = -3
print(solve(nums, goal))
ইনপুট
[0,1,2,3,4], [[3,1],[1,3],[5,6]]
আউটপুট
2
