1 like 0 dislike
232 views
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
in Algorithms and Problems by Expert (17,730 points) | 232 views

1 Answer

1 like 0 dislike
Best answer

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);
by (470 points)
selected by
0 0
Awesome and to the point.