पायथन में ऐरे में विचलन को कम करने का प्रोग्राम

मान लीजिए हमारे पास एक ऐरे nums है। हम ऐरे के किसी भी एलिमेंट पर किसी भी संख्या में दो प्रकार के ऑपरेशन कर सकते हैं:

सम एलिमेंट के लिए, इसे 2 से विभाजित करें।
विषम एलिमेंट के लिए, इसे 2 से गुणा करें।

अब ऐरे का विचलन ऐरे में किन्हीं दो एलिमेंट के बीच अधिकतम अंतर है। हमें कुछ ऑपरेशन करने के बाद ऐरे में न्यूनतम विचलन ढूंढना है। उदाहरण के लिए, यदि इनपुट nums = [6,3,7,22,5] है, तो आउटपुट 5 होगा क्योंकि हम एक ऑपरेशन में अपना ऐरे [6,6,7,22,5] बना सकते हैं और दूसरे ऑपरेशन में [6,6,7,22,10], और दूसरे ऑपरेशन में [6,6,7,11,10], अब विचलन 11-6 = 5 है।

हल करने के चरण

nums सूची को सॉर्ट करें।
max_v := nums का अधिकतम एलिमेंट
min_v := nums का न्यूनतम एलिमेंट
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 := 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]