Dada una array arr[] que consta de N enteros positivos, la tarea es imprimir la cantidad mínima de pasos necesarios para hacer que la array sea tal que todos los elementos sean iguales realizando las siguientes operaciones en la array cualquier cantidad de veces (posiblemente 0).
- Operación-1: seleccione cualquier prefijo arr[1…k] tal que max (arr[1], arr[2], …, arr[k]) = arr[k] y establezca arr[i] = arr[k] para todo i en el rango [1,k−1] .
- Operación-2: seleccione cualquier segmento [L, R] y desplace el segmento cíclicamente hacia la izquierda manteniendo los demás elementos sin cambios.
Ejemplos:
Entrada: arr[] = {1, 2, 12, 20, 18, 19}
Salida: 2
Explicación: Se puede resolver en dos pasos:
En el primer paso, aplique la operación 2 eligiendo L = 4 y R = 6 da como resultado la secuencia {1, 2, 12, 18, 19, 20}.
En el segundo paso, aplique la operación 1 en el prefijo arr{1, 2, 12, 18, 19, 20} que convierte arr en {20, 20, 20, 20, 20} donde todos los elementos son iguales.Entrada: arr[] = {2, 2, 2, 2}
Salida: 0
Explicación: los elementos de la array son todos iguales.
Enfoque: El problema dado se puede resolver usando la siguiente observación:
- Si todos los elementos son iguales no es necesario realizar ninguna operación.
- Si el máximo de la array es al final, solo realizar la operación 1 para toda la array hace que todos los elementos sean iguales.
- Si el máximo está en algún lugar antes de la última posición, diga j. Luego, realizar la operación 2 en el segmento [j, N] y luego la operación 1 para el prefijo [1, N] hace que todos los elementos sean iguales.
Entonces, según la observación anterior, la respuesta puede ser 0, 1 o 2. Siga los pasos que se mencionan a continuación.
- Iterar la array y encontrar el máximo de la array.
- Si todos los elementos de la array son iguales, devuelve 0.
- Si el máximo está presente al final de la array, la respuesta es 1, como se muestra en la observación.
- Si estos dos no son el caso, entonces la respuesta es 2.
A continuación se muestra la implementación del enfoque anterior:
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 equal 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 = 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 Code int 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 equal def 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 Code if __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 approach using 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 equal function 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 Code let arr = [1, 2, 12, 20, 18, 19]; let N = arr.length; solve(arr, N); // This code is contributed by saurabh_jaiswal. </script>
2
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por athakur42u y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA