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.

You should choose one, either Java or JavaScript, both are completely different languages. And then you should focus on the problem, what can you not do that you need to be doing? — Polygnome, Sep 30 '20 at 15:43
use PriorityQueue. the max will be at the top. change it. the PriorityQueue will be re-arnge itself. repeat this k times. this take only n log n + k log n. at the end you can sum. [PriorityQueue java](https://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html) — ibra, Sep 30 '20 at 15:47
This is a javascript problem. Java has no relationship to java (or as one person here says it, as much relationship as "pain" does to "painting"). — NomadMaker, Sep 30 '20 at 16:29

ibra · Accepted Answer · 2020-09-30T16:32:57.847

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.
1. For k iteration: get the element at the top (poll()), do the operation, and add it again to the max heap.
1. 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.

I thought , At the first you mentioned Java !!, Any way, the algorithm is exactly the same for javascript look at [PriorityQueue in JavaScript](https://stackoverflow.com/questions/42919469/efficient-way-to-implement-priority-queue-in-javascript) — ibra, Sep 30 '20 at 16:13

score 0 · Answer 2 · answered Jan 26 '21 at 02:17

const minSum = (arr, k) => {
  let newArr = arr
  while (k--) {
    let max;
    let newValue;
    let replacingIndex;
    max = Math.max.apply(Math, newArr);
    newValue = Math.ceil(max / 2);
    replacingIndex = newArr.findIndex((value) => value === max);
    newArr[replacingIndex] = newValue;
  }
  return newArr.reduce((a, b) => {a + b})
}

Javascript: finding minimum sum after k operations

2 Answers2