How to make all the array elements equal using increment/decrement operations

CodeChef-DSA-learners
1

Consider an array a=[1, 1, 2, 2, 3, 3].Two operations are required to make the array equal that is decrement both the three’s by 1 and add it to both the one’s.

I tried the code given in this link: Minimum Increment / decrement to make array elements equal - GeeksforGeeks

but it’s not giving the correct answer.

What is the simplest code to solve this

2

Hi, can you share the link to the question you are trying to solve, going through question helps others to understand the problem better.

3

There is no link to the question. It appeared in an online assessment(TCS NQT).

4

The geeksforgeeks code treats additions and subtractions as independent operations, so it counts 4 operations for your a=[1, 1, 2, 2, 3, 3] input.

Is your online assessment already over? I don’t feel like helping if it’s still ongoing.

5

The online assessment is already over. Few testcases hadn’t passed in the exam that’s why I wanted an answer.

So according to the GFG code should I divide by 2 to get the answer?

6

What exactly can be done with a single operation?

  • Do we pick a pair of different indexes for each operation to increment one value and decrement the other? If yes, then the key observation is that each operation does not change the total sum of all elements in the array (let’s say the total sum is S and it remains the same). If solution exists and we are able to make all elements equal, then S has to be divisible by the size of the array N and each element becomes equal to X = S / N. Then the number of individual increments and decrements can be obtained by iterating over all elements of the array \sum\limits_{i=1}^N \vert {A_i-X} \vert. To get your answer (the number of increment/decrement pairs), just divide this sum by 2. And again, making the array equal is impossible if S is not divisible by N, one of the examples of a bad array is a=[2, 3]

  • Or do we pick the type of operation (increment or decrement) and multiple array indexes to update them all as a single operation? If yes, then the key observation is that a single operation can either decrease the maximum value of the array by 1 or increase the minimum value of the array by 1. The answer is just the difference between the maximum and the minimum array values. There’s no way to reduce the number of operations further.