TransWikia.com

Minimum count to make equal Array

Stack Overflow Asked on December 1, 2020

This question is taken from this link.
Given a non-empty integer array of size n, find the minimum number of moves required to make all array elements equal, where a move is incrementing n – 1 elements by 1.

Example:

Input:
[1,2,3]

Output:
3

Explanation:

Only three moves are needed (remember each move increments two elements):

[1,2,3]  =>  [2,3,3]  =>  [3,4,3]  =>  [4,4,4]

The links has below working solution:

class Solution {
    public int minMoves(int[] nums) {
       int total=0, least=numbers[0];
        for (int i = 0; i < numbers.length; i++) {
            if (numbers[i] < least) {
                least = numbers[i];
            }
            total = total + numbers[i];
        }
        return total - least * numbers.length; 
    }
}

Here least is the minimum from array, and total is sum of all elements from the array.

But I am wondering how the value total - least * numbers.length is solving this problem. what formula is this? can someone please explain?

4 Answers

I have been thinking about the formula -

number of moves = sum total - least * numbers.length

This is how I tried and understand this. Let's say, we have 3 numbers - a, b, c. Minimum of those numbers is a. Now, we can write the sum of these numbers like -

Sum Total = a + b + c = 3a + (b - a) + (c - a)

Total Number of moves should be the sum of difference between the other numbers. So, formula becomes -

Sum Total = 3a + number of moves

Thus, it turns out to be -

number of moves = Sum Total - 3a

Answered by SKumar on December 1, 2020

Well, thinking from a 'modulo' perspective, incrementing n-1 elements of the array would be the same as decrementing a single value of the array (in the context of this problem). For example, if you increment the first 3 elements of [1;1;1;2] to [2;2;2;2] it would be exactly the same as decrementing the last element: [1;1;1;2] becomes [1;1;1;1], which satisfies the condition of the problem.

So, the problem becomes a bit easier to understand: at each move you can decrement a single element. So, you need to decrement all elements from the list, until they are equal to the minimum element of the list. Then, the number of moves becomes S - length * min as you would have to decrement S times to bring all elements to 0, but you could save some moves by reaching an array having only the minimum value (length * min)

Answered by AndreiXwe on December 1, 2020

// We have number 123
// Algorythm is simple: (add all digits to each other)
// and substract (smallest digit * quantity of digits)
let moves = (1 + 2 + 3) - (1*3);
console.log(moves);

// 622
moves = (6 + 2 + 2) - (2*3);
console.log(moves);

// 183
moves = (1 + 8 + 3) - (1*3);
console.log(moves);

So we can write simple function to calculate moves for numbers

// Moves function
const getMoves = (num) => {
  // Get summ of all digits
  const sum = String(num).split('').reduce((a, c) => Number(a) + Number(c));
  // Get minimum digit
  const min = String(num).split('').reduce((a, c) => a > c ? c : a);
  // Get number length
  const nl = String(num).length;
  // Calculate and return moves
  return sum - (min * nl);
};

// Test
console.log(getMoves(123));
console.log(getMoves(622));
console.log(getMoves(183));

And finally, write alternative to your function to work with arrays

// Moves function
const getMoves = (arr) => {
  const sum = arr.reduce((a, c) => a + c);
  const min = arr.reduce((a, c) => a > c ? c : a);
  return sum - (min * arr.length);
};

// Test
console.log(getMoves([1,2,3]));
console.log(getMoves([6,2,2]));
console.log(getMoves([1,8,3]));

Answered by tarkh on December 1, 2020

'Incrementing n - 1 elements by 1' equal 'decrementing 1 element by 1 (and increment each element, but it doesn't have any sense)'.

You need to decrement each element on the difference between it and the minimum to get all element equal min value.

So, first you should find the minimum value from array, and then get sum of all element and subtract min element multiply count of elements.

Answered by Andrew Blagij on December 1, 2020

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP