The Minimum Number Of Moves | CodeChef Solution

Hello coders, today we are going to solve The Minimum Number Of Moves CodeChef Solution whose Problem Code is SALARY.

Task

Little chief has his own restaurant in the city. There are N workers there. Each worker has his own salary. The salary of the i-th worker equals to W_i (i = 1, 2, …, N). Once, chief decided to equalize all workers, that is, he wants to make salaries of all workers to be equal. But for this goal he can use only one operation: choose some worker and increase by 1 salary of each worker, except the salary of the chosen worker. In other words, the chosen worker is the loser, who will be the only worker, whose salary will be not increased during this particular operation. But loser-worker can be different for different operations, of course. Chief can use this operation as many times as he wants. But he is a busy man. That’s why he wants to minimize the total number of operations needed to equalize all workers. Your task is to find this number.

Input Format

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. The first line of each test case contains a single integer N denoting the number of workers. The second line contains N space-separated integers W₁, W₂, …, W_N denoting the salaries of the workers.

Output Format

For each test case, output a single line containing the minimum number of operations needed to equalize all workers.

Constraints

• 1 ≤ T ≤ 100
• 1 ≤ N ≤ 100
• 0 ≤ W_i ≤ 10000 (10⁴)

Example

Sample Input

2
3
1 2 3
2
42 42

Sample Output

3
0

Explanation

Example Case 1. Chief can equalize all salaries in 3 turns:

Turn ID	IDs of involved workers	Salaries after the move
1	1 2	2 3 3
2	1 2	3 4 3
3	1 3	4 4 4

Example Case 2. All salaries are already equal. He doesn’t need to do anything.

Solution – The Minimum Number Of Moves

C++

#include <iostream>
#include <vector>
using namespace std;

int main() {
	// input number of tests
	int T;
	cin >> T;

	// loop over tests
	for (int t = 0; t < T; ++t) {

		// input number of workers
		int N;
		cin >> N;

		// input their salaries
		vector<int> W(N);
		for (int i = 0; i < N; ++i) {
			cin >> W[i];
		}

		int moves = 0;

		while (true) {
			// checking whether all salaries are equal
			bool equal = true;
			for (int i = 1; i < N ; ++i) {
				if (W[i] != W[0]) {
					equal = false;
				}
			}
			// and stop the process in this case
			if(equal) {
				break;
			}

			// otherwise we find maximum salary
			int maxW = 0;
			for (int i = 0; i < N; ++i) {
				maxW = max(maxW, W[i]);
			}

			// and decrease by 1 all maximum salaries
			// increasing by 1 the answer after each decreased salary
			for (int i = 0; i < N; ++i) {
				if (W[i] == maxW) {
					W[i]--;
					moves++;
				}
			}
		}

		cout << moves << endl;
	}
}

Python

t = int(input())
while(t):
  N=int(input())
  salaries=list(map(int,input().split()))
  print(sum(salaries) - (N * min(salaries)))
  t-=1

Java

/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;
import java.util.Collections;
import java.util.Arrays;
/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
	public static void main (String[] args) throws java.lang.Exception
	{
	    Scanner s=new Scanner(System.in);
	    int i=0;
		int ans;
	    int cases=s.nextInt();
		while(cases-- > 0)
		{
		  ans=0;
		  int workers = s.nextInt();
		  int values[] = new int[workers];
	    for(i=0;i<workers;i++)
		{
			values[i] = s.nextInt();
		}
		Arrays.sort(values);
		for(i=workers-1;i>0;i--){
			ans+= (values[i]-values[i-1])*(workers-i);
		}
		System.out.println(ans);
		}
	}
}

Disclaimer: The above Problem (The Minimum Number Of Moves) is generated by CodeChef but the Solution is Provided by CodingBroz. This tutorial is only for Educational and Learning Purpose.