পাইথনে তালিকা রিডিউস করে অবশিষ্ট ক্ষুদ্রতম সংখ্যা বের করার প্রোগ্রাম

ধনাত্মক সংখ্যার একটি তালিকা (nums) দেওয়া আছে। একটি অপারেশনে দুটি মান a এবং b (a ≤ b) বেছে নিয়ে, যদি a < b হয় তবে b-a তালিকায় ফিরে দিতে হবে। যেকোনো সংখ্যক অপারেশন করার পর অবশিষ্ট ক্ষুদ্রতম সংখ্যা বের করতে হবে। তালিকা খালি হলে ০ রিটার্ন করুন।

সমস্যা উদাহরণ

ইনপুট: nums = [2, 4, 5] আউটপুট: 1


ব্যাখ্যা: ৪ এবং ৫ বেছে নিয়ে ১ ফেরত দিন → [২, ১]। তারপর ২ এবং ১ বেছে নিয়ে ১ ফেরত দিন → [১]।

সমাধানের পদ্ধতি (রিকারসিভ ব্যাকট্র্যাকিং / সাবসেট সাম)
এই সমস্যাটি সমতুল্য: তালিকার উপাদানগুলোকে দুটি গ্রুপে ভাগ করে তাদের যোগফলের পার্থক্য ন্যূনতম করা। উত্তর = |sum(S1) - sum(S2)| যেখানে S1 ∪ S2 = nums এবং S1 ∩ S2 = ∅।

s = sum(nums)
f(i, s) ফাংশন: 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)) রিটার্ন করুন


f(0, s) রিটার্ন করুন


পাইথন কোড
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

টেস্ট কেস
ইনপুট: [2, 4, 5]

আউটপুট: 1


নোট: এই রিকারসিভ সমাধান এক্সপোনেনশিয়াল টাইম নেয়। বড় ইনপুটের জন্য DP বা বিটমাস্ক ব্যবহার করা উচিত।