Equal Candies

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
15 upvotes
Asked in company
alibaba

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.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1:

2
5
4 5 1 2 3
4
1 1 1 2

Sample Output 1:

6
1
Explanation of Sample Input 1:
Test case 1:
We can make the final number of candies equal to [3, 3, 3, 3, 3 ] with total changes equal to 6, which is the minimum possible.

Test case 2:
We can make the last element ‘2’ to ‘1’ by decreasing it one time. Hence the minimum changes is 1.

Sample Input 2:

1
1
10

Sample Output 2:

0
Explanation of Sample Input 2:
Test case 1:
As there is only one element, we don't need to change anything.
Hint

Try all possible cases.

Approaches (2)
Brute 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’
Time Complexity

O((Max(candies) - Min(candies)) * N), where ‘N’ is the total number of people, and ‘Max(candies)’, ‘Min(candies)’ is the maximum and minimum elements in the given array.

 

As for each count from Min(candies) to Max(candies), we are iterating over each person to calculate the total difference in candies. Hence the overall time complexity is O((Max(candies) - Min(candies)) * N ).

Space Complexity

O(1)

 

As we are not using any extra space.

Code Solution
(100% EXP penalty)
Equal Candies
Full screen
Console