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
– Polygnome, Commented Sep 30, 2020 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 — ibra
– ibra, Commented Sep 30, 2020 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
– NomadMaker, Commented Sep 30, 2020 at 16:29

ibra · Accepted Answer · 2020-09-30 16:32:57Z

2

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.

edited Sep 30, 2020 at 16:32

answered Sep 30, 2020 at 16:03

ibra

1,3342 gold badges12 silver badges30 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Nimish goel Over a year ago

any suggestion for javascript @ibra

ibra Over a year ago

I thought , At the first you mentioned Java !!, Any way, the algorithm is exactly the same for javascript look at PriorityQueue in JavaScript

nolanjacobson · Accepted Answer · 2021-01-26 02:17:08Z

0

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})
}

answered Jan 26, 2021 at 2:17

nolanjacobson

1653 silver badges9 bronze badges

Collectives™ on Stack Overflow

Javascript: finding minimum sum after k operations

2 Answers 2

2 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related