Flipkart | Find the minimum number of decrements needed to make all array elements equal ?

Question

Expected Time Complexity : O(N) , where 'N'  is the size of the array .

1<=A[i]<=1000000

1<=N<=100000

Example :

2 2 4 5

Output : 5 [ {2,2,2,2} will be the final array with all equal elements]

Note :

1)Algorithm-explanation is must .

2)Adding code is optional .

3)Use Format option while adding code

Answer 1

Algorithm: Since we can only make decrements in the array, the fastest to make all elements equal are to bring down all the elements to the minimum element of the array. After finding the minimum element, our answer will be the sum of difference between each array element and the minimum

Code:  

       int n = sc.nextInt();
       int arr[] = sc.nextArray(n); // Function to read array

       int mini = Integer.MAX_VALUE;
       for(int i : arr)
       {
           mini = Math.min(mini, i);
       } 

       int cnt = 0;
       for(int i : arr) cnt+= (i-mini);
       sc.println(cnt);

Comments

Awesome and to the point.