Given an array arr[] consisting of N positive integers, the task is to print the minimum number of steps required to make the array such that all elements are equal by performing the following operations on the array any number of times (possibly 0).
- Operation-1: Select any prefix arr[1…k] such that max (arr[1], arr[2], …, arr[k]) = arr[k] and set arr[i] = arr[k] for all i in range [1,k−1].
- Operation-2: Select any segment [L, R] and shift the segment cyclically to the left keeping other elements unchanged.
Examples:
Input: arr[] = {1, 2, 12, 20, 18, 19}
Output: 2
Explanation: It can be solved in two steps:
In the first step, apply operation 2 by choosing L = 4 and R = 6 yields the sequence {1, 2, 12, 18, 19, 20}.
In the second step, apply operation 1 on the prefix arr{1, 2, 12, 18, 19, 20} which converts arr into {20, 20, 20, 20, 20} where all elements are equal.Input: arr[] = {2, 2, 2, 2}
Output: 0
Explanation: the elements in the array are all same.
Approach: The given problem can be solved by using the following observation:
- If all the elements are the same no operation needs to be done.
- If the maximum of the array is at last then only performing operation 1 for the whole array makes all the elements equal.
- If the maximum is somewhere before the last position, say j. Then performing operation 2 in segment [j, N] and after that operation 1 for the prefix [1, N] makes all the elements equal.
So based on the above observation, the answer can be 0, 1, or 2. Follow the steps mentioned below.
- Iterate the array and find the maximum from the array.
- If all the elements of the array are the same then return 0.
- If the maximum is present at the end of the array then the answer is 1 as shown in the observation.
- If these two are not the case then the answer is 2.
Below is the implementation of the above approach:
C++
// C++ code to implement the above approach#include <bits/stdc++.h>using namespace std;// Function to print the minimum number// of steps required to make all// the elements are equalvoid solve(int arr[], int N){ // Initially assume all elements // are equal bool isEqual = true; // For finding the largest element int maxi = arr[0]; // Loop to iterate through the array for (int i = 1; i < N; i++) { // If any element is not equal // than previous element, mark // it as false if (arr[i] != arr[i - 1]) { isEqual = false; } // Storing greater element maxi = max(maxi, arr[i]); } // If all the elements are equal if (isEqual) { cout << "0"; } // If max element is found // at the last index else if (maxi == arr[N - 1]) { cout << "1"; } // If max element is found // other than the last index else { cout << "2"; }}// Driver Codeint main(){ int arr[] = { 1, 2, 12, 20, 18, 19 }; int N = sizeof(arr) / sizeof(arr[0]); solve(arr, N); return 0;} |
Java
/*package whatever //do not write package name here */import java.io.*;class GFG { // Function to print the minimum number // of steps required to make all // the elements are equal static void solve(int arr[], int N) { // Initially assume all elements // are equal boolean isEqual = true; // For finding the largest element int maxi = arr[0]; // Loop to iterate through the array for (int i = 1; i < N; i++) { // If any element is not equal // than previous element, mark // it as false if (arr[i] != arr[i - 1]) { isEqual = false; } // Storing greater element maxi = Math.max(maxi, arr[i]); } // If all the elements are equal if (isEqual) { System.out.println("0"); } // If max element is found // at the last index else if (maxi == arr[N - 1]) { System.out.println("1"); } // If max element is found // other than the last index else { System.out.println("2"); } } // Driver Code public static void main(String[] args) { int arr[] = { 1, 2, 12, 20, 18, 19 }; int N = arr.length; solve(arr, N); }}// This code is contributed by Potta Lokesh |
Python3
# Python3 code to implement the above approach # Function to print the minimum number# of steps required to make all# the elements are equaldef solve(arr, N): # Initially assume all elements # are equal isEqual = True # For finding the largest element maxi = arr[0] # Loop to iterate through the array for i in range(1, N): # If any element is not equal # than previous element, mark # it as false if (arr[i] != arr[i - 1]): isEqual = False # Storing greater element maxi = max(maxi, arr[i]) # If all the elements are equal if (isEqual): print("0") # If max element is found # at the last index elif (maxi == arr[N - 1]): print("1") # If max element is found # other than the last index else: print("2") # Driver Codeif __name__=="__main__": arr = [ 1, 2, 12, 20, 18, 19 ] N = len(arr) solve(arr, N)# This code is contributed by Akash Jha |
C#
// C# code to implement the above approachusing System;class GFG { // Function to print the minimum number // of steps required to make all // the elements are equal static void solve(int[] arr, int N) { // Initially assume all elements // are equal bool isEqual = true; // For finding the largest element int maxi = arr[0]; // Loop to iterate through the array for (int i = 1; i < N; i++) { // If any element is not equal // than previous element, mark // it as false if (arr[i] != arr[i - 1]) { isEqual = false; } // Storing greater element maxi = Math.Max(maxi, arr[i]); } // If all the elements are equal if (isEqual) { Console.WriteLine("0"); } // If max element is found // at the last index else if (maxi == arr[N - 1]) { Console.WriteLine("1"); } // If max element is found // other than the last index else { Console.WriteLine("2"); } } // Driver Code public static void Main() { int[] arr = { 1, 2, 12, 20, 18, 19 }; int N = arr.Length; solve(arr, N); }}// This code is contributed by Saurabh Jaiswal |
Javascript
<script>// Javascript code to implement the above approach// Function to print the minimum number// of steps required to make all// the elements are equalfunction solve(arr, N){ // Initially assume all elements // are equal let isEqual = true; // For finding the largest element let maxi = arr[0]; // Loop to iterate through the array for (let i = 1; i < N; i++) { // If any element is not equal // than previous element, mark // it as false if (arr[i] != arr[i - 1]) { isEqual = false; } // Storing greater element maxi = Math.max(maxi, arr[i]); } // If all the elements are equal if (isEqual) { document.write("0"); } // If max element is found // at the last index else if (maxi == arr[N - 1]) { document.write("1"); } // If max element is found // other than the last index else { document.write("2"); }}// Driver Codelet arr = [1, 2, 12, 20, 18, 19];let N = arr.length;solve(arr, N);// This code is contributed by saurabh_jaiswal.</script> |
Output
2
Time Complexity: O(N)
Auxiliary Space: O(1)
Take a part in the ongoing discussion
