Python प्रोग्राम - दी गई ऑपरेशन से सूची को कम करके सबसे छोटी शेष संख्या खोजें

सकारात्मक संख्याओं की सूची nums दी गई है। एक ऑपरेशन पर विचार करें जहां हम किन्हीं दो मान a और b को हटाते हैं जहां a <= b और यदि a < b मान्य है, तो b - a को वापस सूची nums में डालते हैं। यदि हम कोई भी संख्या में ऑपरेशन कर सकते हैं, तो हमें सबसे छोटी शेष संख्या खोजनी है जो हम प्राप्त कर सकते हैं। यदि सूची खाली हो जाती है, तो 0 लौटाएं।

उदाहरण

इनपुट: nums = [2, 4, 5]

आउटपुट: 1

व्याख्या: हम 4 और 5 चुन सकते हैं फिर 1 वापस डालकर [2, 1] प्राप्त करें। अब 2 और 1 चुनकर [1] प्राप्त करें।

एल्गोरिदम (रिकर्सिव - सबसेट सम समस्या)

1. s := sum(nums)
2. f(i, s) फंक्शन परिभाषित करें:
   • यदि i >= len(nums): s लौटाएं
   • n := nums[i]
   • यदि s - 2 * n < 0: f(i + 1, s) लौटाएं
   • min(f(i + 1, s - 2 * n), f(i + 1, s)) लौटाएं
3. मुख्य विधि से f(0, s) लौटाएं

Python कार्यान्वयन

def solve(nums):
    s = sum(nums)
    def f(i, s):
        if i >= len(nums):
            return s
        n = nums[i]
        if s - 2 * n < 0:
            return f(i + 1, s)
        return min(f(i + 1, s - 2 * n), f(i + 1, s))
    return f(0, s)

nums = [2, 4, 5]
print(solve(nums))  # आउटपुट: 1

इनपुट/आउटपुट

Input: [2, 4, 5]
Output: 1

नोट: यह समस्या सबसेट सम समस्या के बराबर है। हम दो सबसेट में विभाजित करने की कोशिश कर रहे हैं जिनका अंतर न्यूनतम हो।