পাইথনে অ্যারে ডевиয়েশন ন্যূনতম করার প্রোগ্রাম

আমাদের একটি অ্যারে nums আছে। আমরা অ্যারেতে যেকোনো উপাদানের ওপর দুই ধরনের অপারেশন যেকোনো সংখ্যক বার পারফর্ম করতে পারি:

• সম উপাদান হলে ২ দিয়ে ভাগ করুন

• বিজোড় উপাদান হলে ২ দিয়ে গুন করুন

এখন অ্যারের ডেভিয়েশন হলো অ্যারেতে যেকোনো দুটি উপাদানের মধ্যকার সর্বাধিক পার্থক্য। আমাদের কিছু অপারেশন করার পর অ্যারেতে ন্যূনতম ডেভিয়েশন কত হতে পারে সেটা বের করতে হবে।

উদাহরণস্বরূপ, ইনপুট nums = [6,3,7,22,5] হলে আউটপুট হবে 5 কারণ আমরা অ্যারেটিকে এক অপারেশনে [6,6,7,22,5] বানাতে পারি, দ্বিতীয় অপারেশনে [6,6,7,22,10], এবং অন্য এক অপারেশনে [6,6,7,11,10], এখন ডেভিয়েশন ১১-৬ = ৫।

সমাধানের ধাপসমূহ (হিপ / প্রায়োরিটি কিউ)

• nums লিস্টটি সর্ট করুন

• max_v := nums-এর সর্বাধিক এলিমেন্ট

• min_v := nums-এর ন্যূনতম এলিমেন্ট

• heapq.heapify(nums)

• res := max_v - min_v

• nums[0] বিজোড় থাকাকালীন লুপ চালান:

  • v := heapq.heappop(nums)

  • v := 2 * v

  • heapq.heappush(nums, v)

  • min_v := nums[0]

  • max_v := max(v, max_v)

  • res := min(res, max_v - min_v)

• nums := [-n for n in nums] (নেগেটিভ করুন)

• heapq.heapify(nums)

• nums[0] জোড় থাকাকালীন লুপ চালান:

  • v := -heapq.heappop(nums)

  • v := v // 2

  • heapq.heappush(nums, -v)

  • max_v := -nums[0]

  • min_v := min(min_v, v)

  • res := min(res, max_v - min_v)

• res রিটার্ন করুন

উদাহরণ

নিচের ইমপ্লিমেন্টেশনটি দেখুন ভালোভাবে বুঝার জন্য:

import heapq
def solve(nums):
    nums.sort()
    max_v, min_v = nums[-1], nums[0]
    heapq.heapify(nums)
    res = max_v - min_v
    while nums[0] % 2 == 1:
        v = heapq.heappop(nums)
        v = 2 * v
        heapq.heappush(nums, v)
        min_v = nums[0]
        max_v = max(v, max_v)
        res = min(res, max_v - min_v)
    nums = [-n for n in nums]
    heapq.heapify(nums)
    while nums[0] % 2 == 0:
        v = -heapq.heappop(nums)
        v = v // 2
        heapq.heappush(nums, -v)
        max_v = -nums[0]
        min_v = min(min_v, v)
        res = min(res, max_v - min_v)
    return res

nums = [6,3,7,22,5]
print(solve(nums))

ইনপুট

[6,3,7,22,5]

আউটপুট

5