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?

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

Get help from others!

Recent Answers

- Peter Machado on Why fry rice before boiling?
- haakon.io on Why fry rice before boiling?
- Lex on Does Google Analytics track 404 page responses as valid page views?
- Joshua Engel on Why fry rice before boiling?
- Jon Church on Why fry rice before boiling?

Recent Questions

- How can I transform graph image into a tikzpicture LaTeX code?
- How Do I Get The Ifruit App Off Of Gta 5 / Grand Theft Auto 5
- Iv’e designed a space elevator using a series of lasers. do you know anybody i could submit the designs too that could manufacture the concept and put it to use
- Need help finding a book. Female OP protagonist, magic
- Why is the WWF pending games (“Your turn”) area replaced w/ a column of “Bonus & Reward”gift boxes?

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