Minimize replacements of leftmost largest array element required to make all array elements equal

Minimize replacements of leftmost largest array element required to make all array elements equal

Given an array arr[] consisting of N integers, the task is to make all array elements equal by replacing the leftmost largest element of the array with the largest element strictly smaller than the current maximum minimum number of times.

Examples:

Input: arr[] = { 1, 1, 2, 2, 3}
Output: 4
Explanation: Following operations reduces the required number of operations to minimum:

1. Leftmost largest array element is arr[4]( = 3). Replacing it with the largest element smaller than the current largest, arr[3] (= 2), the array modifies to {1, 1, 2, 2, 2}.
2. Leftmost largest element of the array is arr[2]( = 2). Replacing it with the largest element smaller than the current largest, arr[1] (= 1), the array modifies to {1, 1, 1, 2, 2}.
3. Leftmost largest element of the array is arr[3]( = 2), replacing it with the largest element smaller than the current largest, arr[1] (= 1), the array modifies to {1, 1, 1, 1, 2}.
4. Leftmost largest element of the array is arr[4]( = 2). Replacing it with the largest element smaller than the current largest, arr[1] (=1), the array modifies to {1, 1, 1, 1, 1}

Therefore, a minimum of 4 moves are needed.

Input: arr[] = {5, 1, 3} 
Output: 3

Approach: The problem can be solved by sort the array in descending order based on the observations that at each step, an array element will replace all the elements that are larger than the current array element. Follow the steps to solve the problem:

• Sort the array in descending order.
• Initialize a variable, say count as 0, to count the total number of moves required.
• Iterate over the range [1, N – 1] using a variable i and perform the following steps:
  • If arr[i] != arr[i – 1], then increment count by i.
• Finally, after completing the above steps, the print value obtained in count as the answer.

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h> using namespace std;    int reductionOperations(int arr[], int N) {          sort(arr, arr + N, greater<int>());             int count = 0;             for (int i = 1; i < N; i++) {                     if (arr[i - 1] != arr[i]) {                             count += i;         }     }             return count; }    int main() {          int arr[] = { 1, 1, 2, 2, 3 };     int N = sizeof(arr) / sizeof(arr[0]);             cout << reductionOperations(arr, N); }

Time Complexity: O(N * log(N))
Auxiliary Space: O(1)

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready.  To complete your preparation from learning a language to DS Algo and many more,  please refer Complete Interview Preparation Course.

In case you wish to attend live classes with industry experts, please refer DSA Live Classes

Adblock test (Why?)

Original page link

Best Cool Tech Gadgets

Top favorite technology gadgets