Minimice los pasos para hacer que todos los elementos de Array sean iguales cambiando cíclicamente un segmento o reemplazando el prefijo por el máximo

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++ 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;
}

/*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 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# 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

<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)