Minimize steps to make Array elements equal by using giving operations
Given an arr[] of length N. Then the task is to find minimum steps to make all the elements of the given array equal. Two types of operations can be performed as given below:
- Choose a prefix of size K, where arr[K] = max element in that chosen sub-array and convert all elements equal to max.
- Choose any sub-array and left-rotate it once.
Examples:
Input: N = 2, arr[] = {34, 34}
Output: 0
Explanation: All the elements are equal already. Therefore, No need to apply operations on it, Hence cost is zero.Input: N = 3, arr[] = {1, 2, 3}
Output: 1
Explanation:
First operation: Choose prefix sub-array {A1, A2, A3} in which arr[3] = max element in sub-array and equal all the elements with max = {3, 3, 3}. Therefore, minimum cost is 1.
Approach: The problem can be solved based on the following observation:
We can solve any case at most 2 operations. For more clarification see the concept of approach and its illustration below.
If the max element is present at last index of the arr[], Then all the elements can be make equal by using the first operation only. From this we can conclude that the optimal choice is to place the maximum element of the array at the last index. We can shift max element to the last index using only one instance of second operation.
So there are three cases:
- If max = min in arr[], Then arr[] elements are equal already. Therefore, minimum cost is 0.
- If max element is present at last index of arr[], Then elements can be make equal by applying First operation. Therefore, minimum cost is 1.
- Rest of the cases except above two will take two operations. Therefore, minimum cost is 2.
Follow the below steps to implement the idea:
- Create variables max, min, and max_index for storing the maximum, minimum element, and index of the maximum element respectively.
- Then check for the below conditions:
- If max = min, Then the minimum cost is 0.
- If max_index = N, Then the minimum cost is 1.
- The rest of the cases will have a minimum cost equal to 2.
Below is the implementation of the above approach.
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Function for calculating // minimum cost int minimum_cost( int N, int ayami[]) { // Variable to store maximum // element of arr[] int max = INT_MIN; // Variable to store minimum // element of arr[] int min = INT_MAX; // Variable to store index of // maximum element of arr[] int max_index = 0; // Loop for traversing on arr[] for ( int i = 0; i < N; i++) { // Upading max if element // greater than max is found max = ayami[i] > max ? ayami[i] : max; // Upading max if element less // than min is found min = ayami[i] < min ? ayami[i] : min; // Storing index of max element if (max == ayami[i]) { max_index = i; } } // Checking that all the elements // are equal already if (max == min) { return 0; } // Checking that max element is // present at last index or not else if (max == ayami[N - 1]) { return 1; } // Rest of the cases except // above two cases else { return 2; } } // Driver Code int main() { // Input value of N int N = 5; // Input arr[] int ayami[] = { 1, 8, 5, 4, 3 }; // Printing minimum cost by calling // minimum_cost function cout << minimum_cost(N, ayami); return 0; } // This code is contributed by sanjoy_62. |
Java
// Java code to implement the approach import java.io.*; import java.lang.*; import java.util.*; class GFG { // Driver function public static void main(String[] args) throws java.lang.Exception { // Input value of N int N = 5 ; // Input arr[] int [] ayami = { 1 , 8 , 5 , 4 , 3 }; // Printing minimum cost by calling // minimum_cost function System.out.println(minimum_cost(N, ayami)); } // Function for calculating // minimum cost static int minimum_cost( int N, int [] ayami) { // Variable to store maximum // element of arr[] int max = Integer.MIN_VALUE; // Variable to store minimum // element of arr[] int min = Integer.MAX_VALUE; // Variable to store index of // maximum element of arr[] int max_index = 0 ; // Loop for traversing on arr[] for ( int i = 0 ; i < N; i++) { // Upading max if element // greater than max is found max = ayami[i] > max ? ayami[i] : max; // Upading max if element less // than min is found min = ayami[i] < min ? ayami[i] : min; // Storing index of max element if (max == ayami[i]) { max_index = i; } } // Checking that all the elements // are equal already if (max == min) { return 0 ; } // Checking that max element is // present at last index or not else if (max == ayami[N - 1 ]) { return 1 ; } // Rest of the cases except // above two cases else { return 2 ; } } } |
Python3
# Python code to implement the approach # Function for calculating # minimum cost def minimum_cost(N, ayami): # Variable to store maximum # element of arr[] Max = float ( "-inf" ) # Variable to store minimum # element of arr[] Min = float ( "inf" ) # Variable to store minimum # element of arr[] max_index = 0 # Loop for traversing on arr[] for i in range (N): # Updating max if element # greater than max is found Max = ayami[i] if ayami[i] > Max else Max # Updating max if element less # than min is found Min = ayami[i] if ayami[i] < Min else Min # Storing index of max element if ( Max = = ayami[i]): max_index = i # Checking that all the elements # are equal already if ( Max = = Min ): return 0 # Checking that max element is # present at last index or not elif ( Max = = ayami[N - 1 ]): return 1 # Rest of cases expect # above two cases else : return 2 # Input value of N N = 5 # Input arr[] ayami = [ 1 , 8 , 5 , 4 , 3 ] # Printing minimum cost by calling minimum_cost function print (minimum_cost(N, ayami)) # This code is contributed by lokeshmvs21. |
C#
// C# code to implement the approach using System; public class GFG{ // Function for calculating // minimum cost static int minimum_cost( int N, int [] ayami) { // Variable to store maximum // element of arr[] int max = Int32.MinValue; // Variable to store minimum // element of arr[] int min = Int32.MaxValue; // Variable to store index of // maximum element of arr[] int max_index = 0; // Loop for traversing on arr[] for ( int i = 0; i < N; i++) { // Upading max if element // greater than max is found max = ayami[i] > max ? ayami[i] : max; // Upading max if element less // than min is found min = ayami[i] < min ? ayami[i] : min; // Storing index of max element if (max == ayami[i]) { max_index = i; } } // Checking that all the elements // are equal already if (max == min) { return 0; } // Checking that max element is // present at last index or not else if (max == ayami[N - 1]) { return 1; } // Rest of the cases except // above two cases else { return 2; } } static public void Main (){ // Input value of N int N = 5; // Input arr[] int [] ayami = { 1, 8, 5, 4, 3 }; // Printing minimum cost by calling // minimum_cost function Console.WriteLine(minimum_cost(N, ayami)); } } // This code is contributed by lokesh |
Javascript
// JS code // Function for calculating // minimum cost function minimum_cost(N,ayami) { // Variable to store maximum // element of arr[] let max = Number.MIN_VALUE; // Variable to store minimum // element of arr[] let min = Number.MAX_VALUE; // Variable to store index of // maximum element of arr[] let max_index = 0; // Loop for traversing on arr[] for (let i = 0; i < N; i++) { // Upading max if element // greater than max is found max = ayami[i] > max ? ayami[i] : max; // Upading max if element less // than min is found min = ayami[i] < min ? ayami[i] : min; // Storing index of max element if (max == ayami[i]) { max_index = i; } } // Checking that all the elements // are equal already if (max == min) { return 0; } // Checking that max element is // present at last index or not else if (max == ayami[N - 1]) { return 1; } // Rest of the cases except // above two cases else { return 2; } } let N = 5; // Input arr[] let ayami = [ 1, 8, 5, 4, 3 ]; // Printing minimum cost by calling // minimum_cost function console.log(minimum_cost(N, ayami)); // This code is contributed by ksam24000 |
2
Time Complexity: O(N)
Auxiliary Space: O(1)
Related Articles:
Contact Us