Javascript: finding minimum sum after k operations

Question

An array is manipulated k times so that each time the max value is divided by 2 and rounded up. I need to find its minimum sum after these k manipulations. k and all numbers in array num > 1. The method minSum receives an array called num and an integer k. The brute Python code that works for me with very bad time complexity is:

function minSum(arr, k) {
    // Write your code here
let sum = 0; 
    while(k !==0){

       
        let max = Math.max(...arr)
        let index = arr.indexOf(max);
         
        max = Math.ceil(max/2);
        arr[index] = max;
        
        k--;
    }
    sum =  arr.reduce((a, b) => a + b, 0);
        console.log(sum);
    return sum;
}

Similar question relate to python is here. More efficient method of finding minimum sum after k operations

but nothing related to Javascript.

Answer 1

Here are the steps (using Java based on your first demand before the change to JavaScript):

• 1. Use max heap (PriorityQueue in reverse order), so the max will be at the top.
• 2. For k iteration: get the element at the top (poll()), do the operation, and add it again to the max heap.
• 3. At the end, just sum.

    public static int minSumJava_using_pqueue(int arr[], int k)
    {
        PriorityQueue<Integer> pq = new PriorityQueue<>(10, Collections.reverseOrder());

        for (int val : arr) {
            pq.add(val);
        }

        int new_val;
        for(int i =0; i<k; i++)
        {
            new_val = pq.poll();
            new_val = (int) Math.ceil(new_val/2.0);
            pq.add(new_val);
        }

        int sum = 0;
        for (Integer val: pq) {
            sum += val;
        }
        
        return sum;
    }

Check the source code:

    public static void main(String[] args)
    {
        int k = 4;
        int arr[] = {10,20,7};
        int result = minSumJava_using_pqueue(arr, k);
        System.out.println("min sum = "+ result);
    }

The Result is indeed the same as in your example:

min sum = 14

Note: you can do exactly the same thing with JavaScript or any other programming language.