Last Updated: 22 Apr, 2021

Equal Candies

Moderate

Asked in company

Solve now

Problem statement

On Christmas Eve, all people at coding ninjas are given some candies but due to some error all people do not get the same number of candies.

You are given an array of size ‘N’ that represents the number of candies given to ‘N’ people. You have to divide candies among all people such that each person receives the same number of candies. For this You can either increase or decrease the number of candies for any person by any amount. Your task is to minimise total increase/decrease for each person i.e. If you increase or decrease ‘Xi’ number of candies for the person ‘i’ ( 1 <= ‘i’ <= ‘N’), then the sum of all ‘Xi’ should be minimum.

Input Format :

The first line contains an integer 'T' which denotes the number of test cases or queries to be run.

The first line of each test case contains an integer ‘N’ representing the total number of people.

The second line of each test case contains ‘N’ space-separated integers representing the initial count of candies for each person.

Output Format :

For each test case, print an integer representing the minimum possible total increase/decrease in candies count to make equal number of candies for each person.

The output of each test case will be printed in a separate line.

Note :

You do not need to input or print anything, and it has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 5
1 <= N <= 5000
1 <= candies[i] <= 10 ^ 9

Where ‘candies[i]’ is the initial count of candies for each person 'i' from 1 to ‘N’.

Time Limit : 1sec

Solve now

Approaches

01 Approach

Let's suppose that all people will get ‘X’ number of candies after the operations are performed. We can simply iterate over all possible ‘X’ and find the minimum total increase/decrease in the number of candies for each ‘X’. It can be easily observed that we need to check only such ‘X’ that lies between the between- person with a minimum number of candies to a person with the maximum number of candies

between-person

Algorithm:

Let the given array be ‘candies’.
Declare a variable ‘answer’ to store the minimum difference in candies count.
Run a loop from ‘X’ = min element of ‘candies’ to maximum element of ‘candies’.
- Declare a variable say ‘temp’ to store the total difference in candies when the final candies count is ‘X’.
- Run a loop from ‘i’ = 0 to ‘candies.size’ - 1
  - Increase ‘temp’ by absolute difference between ‘X’ and ‘candies[i]’, i.e. temp += abs(candies[i] - X).
- Update answer to min( ‘answer’, ‘temp’).
Return ‘answer’

Solve now

02 Approach

The idea is to take the median of the given array and make all elements of the array equal to the median. Because we can observe that it is optimal to make all candies as the middle element, in this way we need to make fewer changes in the number of candies. For example, if we have a sorted array say { a1, a2, a3, a4, a5 }, it is optimal to make all elements equal to a3, rather than any other elements like a2 or a4.

Algorithm:

Let the given array be ‘candies’.
Declare a variable ‘answer’ to store the minimum difference in candies count.
Sort the array ‘candies’ in increasing order.
Declare a variable median and store ‘candies[ N / 2]’ in it.
Run a loop from ‘i’ = 0 to ‘candies.size’ - 1
- Increase ‘answer’ by absolute difference between ‘X’ and ‘candies[i]’, i.e. do answer += abs(candies[i] - X).
Return ‘answer’

Solve now