Last Updated: 12 Apr, 2021
Minimum Cost
Easy
Asked in companies
There are ‘N’ numbers of balls in a room that are placed in a row. You are given an array ‘location’ where location[ i ] denotes the location of the ‘i-th’ ball.
You have to move all the balls at the same location, and it is given that you can move a ball from position [ i ] to
1. position[i] + 2 with cost = 0.
2. position[i] + 1 with cost = 1.
Your task is to find the minimum cost required to move all the balls at the same location.
For Example :
If we have three balls placed at [ 1, 3, 4 ]
At first, move the ball from position ‘1’ to position ‘3’ with cost = 0.
Then move the ball from position ‘4’ to position ‘3’ with cost =1.
As the minimum cost = 1, so you need to print 1.
Input Format :
The first line contains a single integer ‘T’ denoting the number of test cases.
Each test case’s first line contains a single integer ‘N’, denoting the number of balls.
The second line of each test case contains ‘N’ space-separated integers denoting the balls’ positions.
Output Format :
For each test case, print a single integer denoting the minimum cost required to move all the balls to the same location.
Print the output of each test case in a separate line.
Note :
You don’t need to print anything. It has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 50
1 <= N <= 10^5
1 <= location[i] <= 10^5
Where location[i] is the location of the ‘i-th’ ball.
Time limit: 1 sec.
Approaches
As moving the ball at location[ i ] to location[ i ] + 2 and location[ i ] - 2 does not cost anything.
So it can be noted that we can move any ball at an even position to any other even position with ‘0’ cost.
And any ball at an odd position to some other odd position with ‘0’ cost.
Now we can move all the balls at even position to ‘0’ and all the balls at the odd position to ‘1’ with no cost.
Now we have to pile all the balls either at ‘0’ or at ‘1’.
Cost of moving all the balls from 0 to 1 = number of balls at 0 i.e number of balls that were at even positions.
Cost of moving all the balls from 1 to 0 = number of balls at 1 i.e number of balls that were at odd positions.
So the minimum cost to move the balls at the same location will be the minimum of the count of balls at even position and count of balls at odd positions.
Algorithm
- Initialize two variables ‘odd’ and ‘even’ with values ‘0’ to store the count of balls at odd and even positions respectively.
- Iterate through the ‘location’ array, i: 0 to N-1
- If location[ i ] is even.
- Increment ‘even’.
- Otherwise
- Increment ‘odd’.
- If location[ i ] is even.
- Return minimum of ‘odd’ and ‘even’.