Minimum Moves to Equal Array Elements Leetcode Solution

Difficulty Level Easy
Frequently asked in Amazon Apple Coursera Factset Indeed JPMorgan Mathworks Microsoft Swiggy
algorithms coding Drawbridge Interview interviewprep LeetCode LeetCodeSolutions Math

Problem Statement

In this problem, we are given an array of integers. Also, we are allowed to perform a certain set of operations on this array. In one operation, we can increment ” n – 1″ (all elements except any one) elements in the array by 1.

We need to find the minimum number of operations required to make all array elements equal.

Example

Array = {1 , 2 , 3}
3
Array = {1 , 1 , 1} PinApproach (Math)

In this problem, the difficulty is to choose the set of numbers you would like to increase by 1 to equal all the array elements. However, increasing ‘N – 1’ elements in the array is the same as decreasing one array element by 1. This is because we do not wish to find out what will be the value of all elements once they are equal, rather we are interested in finding the number of moves. Now, this is intuitive that since our operation is to decrease exactly one element in the array by 1, we need to convert all the elements in the array to the minimum element present in the array(As it doesn’t need to be decreased any further).

Implementation for Minimum Moves to Equal Array Elements Leetcode Solution

C++ Program

#include <bits/stdc++.h>

using namespace std;

int minMoves(vector <int> nums) {
int mn = *min_element(nums.begin() , nums.end()) , moves = 0;
for(int &i : nums)
moves += i - mn;
return moves;
}

int main() {
vector <int> nums = {1 , 2 , 3};
cout << minMoves(nums) << endl;
return 0;
}

Java Program

import java.lang.*;
import java.util.*;

class min_moves {
public static void main(String args[]) {
int[] nums = {1 , 2 , 3};
System.out.println(minMoves(nums));
}

public static int minMoves(int[] nums) {
if(nums.length == 0)
return 0;
int mn = nums;
for(int i = 0 ; i < nums.length ; i++) {
mn = Math.min(mn , nums[i]);
}

int moves = 0;
for(int i = 0 ; i < nums.length ; i++) {
moves += nums[i] - mn;
}

return moves;
}
}
3

Complexity Analysis of Minimum Moves to Equal Array Elements Leetcode Solution

Time Complexity

O(N), N = size of the array. We traverse the whole array once.