Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

Leetcode 2208. Cut the array and halve the minimum number of operations

Give you an array of positive integers nums. In each operation, you can select any number from nums and reduce it to exactly half. (Note that you can continue with halving the number later.) Return the minimum operand that reduces the NUMS array and nums by at least half.

 

Example 1:

Input: nums = [5,19,8,1] Output: 3 Description: The initial sum of NUMs is 5 + 19 + 8 + 1 = 33. Here’s one way to reduce the array sum by at least half: Select the number 19 and reduce it to 9.5. Select the number 9.5 and reduce it to 4.75. Select the number 8 and reduce it to 4. The final array is [5, 4.75, 4, 1], and is 5 + 4.75 + 4 + 1 = 14.75. The sum of nums is reduced by 33 to 14.75 = 18.25, which is more than half of the original sum, 18.25 >= 33/2 = 16.5. We need 3 operations to do that, so return 3. You can prove that you cannot reduce the array sum by at least half with less than three operations.

Example 2:

Input: nums = [3,8,20] Output: 3 Description: The initial sum of NUMs is 3 + 8 + 20 = 31. Here’s one way to reduce the array sum by at least half: Select the number 20 and reduce it to 10. Select the number 10 and reduce it to 5. Select the number 3 and reduce it to 1.5. The final array is [1.5, 8, 5], and 1.5 + 8 + 5 = 14.5. The sum of nums is reduced by 31-14.5 = 16.5, which is more than half of the original sum, 16.5 >= 31/2 = 16.5. We need 3 operations to do that, so return 3. You can prove that you cannot reduce the array sum by at least half with less than three operations.

 

Tip:

1 <= nums.length <= 105 1 <= nums[i] <= 107

Subject analysis

We need to calculate the minimum number of operations to reduce the sum of an array by more than half. The most intuitive way to get the minimum number of operations is to halve the maximum number of operations in the array. Notice that each halving operation requires removing the current value from the array and then putting the halved value into the array. By continuously halving operations until the requirements are met.

The above analysis shows that the minimum number of operations can be obtained by halving the maximum value continuously. Given the size of the array and the range of its values, it is conceivable that sorting through the array would time out. Here we need to use Leetcode which has the @DataStructures-JS /priority-queue library built in. We solve this problem by using the MaxPriorityQueue maximum priority queue.

MaxPriorityQueue enqueue has two parameters priority and element, dequeue queue, toArray queue into an array. You can use toArray to view the queue.

Step by step to achieve

Loop through the total numS array and enqueue the elements, using the toArray method if you want to know the status of the queue.

let total = 0
    let queue = new MaxPriorityQueue()
    let half = 0
    let ans = 0
    for(let i=0; i<nums.length; i++){
        total+=nums[i]
        queue.enqueue(nums[i], nums[i])
    }
    half = total / 2
Copy the code

The minimum number of operations is calculated by continuously entering and leaving the queue

 while (total > half) {
        let { element } = queue.dequeue()
        element /= 2
        total -= element
        queue.enqueue(element, element)
        ans ++
    }
Copy the code

Code implementation

var halveArray = function(nums) {
    let total = 0
    let queue = new MaxPriorityQueue()
    let half = 0
    let ans = 0
    for(let i=0; i<nums.length; i++){
        total+=nums[i]
        queue.enqueue(nums[i], nums[i])
    }
    half = total / 2
    while (total > half) {
        let { element } = queue.dequeue()
        element /= 2
        total -= element
        queue.enqueue(element, element)
        ans ++
    }
    return ans
};
Copy the code