Sunday, June 11, 2017

Minimum Moves to Equal Array Elements



Problem Statement
Given a non-empty integer array of size n, find the minimum number of moves required to make all array elements equal, where a move is incrementing n - 1 elements by 1.

Link to GitHubCode


Example
Input:
[1,2,3]
Output:
3
Explanation:
Only three moves are needed (remember each move increments two elements):
[1,2,3]  =>  [2,3,3]  =>  [3,4,3]  =>  [4,4,4]

Solution

  • Adding 1 to n - 1 elements is the same as subtracting 1 from one element, w.r.t goal of making the elements in the array equal.So, best way to do this is make all the elements in the array equal to the min element. 
          sum(array) - n * minimum
   
public static int get(int arr [])
 {
  if (arr.length == 0 ) return 0;
  int min=arr[0];
  for(int n: arr)
  {
   min=Math.min(min, n);
  }
  int res=0;
  for(int n: arr)
  {
   res+=n-min;
  }
  return res;
 }

No comments:

Post a Comment