Número mínimo de movimientos para hacer que todos los elementos sean iguales

Dada una array que contiene N elementos y un número entero K, se permite realizar la siguiente operación cualquier número de veces en la array dada: 
 

• Inserte el elemento K-th al final de la array y elimine el primer elemento de la array.

La tarea es encontrar el número mínimo de movimientos necesarios para que todos los elementos de la array sean iguales. Imprime -1 si no es posible.
Ejemplos: 
 

Input : arr[] = {1, 2, 3, 4}, K = 4
Output : 3
Step 1: 2 3 4 4
Step 2: 3 4 4 4
Step 3: 4 4 4 4

Input : arr[] = {2, 1}, K = 1
Output : -1
The array will keep alternating between 1, 2 and 
2, 1 regardless of how many moves you apply.

Veamos las operaciones con respecto al arreglo original, primero copiamos a[k] hasta el final, luego a[k+1], y así sucesivamente. Para asegurarnos de que solo copiamos elementos iguales, todos los elementos en el rango K a N deben ser iguales. 
Entonces, para encontrar el número mínimo de movimientos, necesitamos eliminar todos los elementos en el rango de 1 a K que no sean iguales a a[k]. Por lo tanto, debemos seguir aplicando operaciones hasta que alcancemos el término más a la derecha en el rango 1 a K que no es igual a a[k].
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ Program to find minimum number of operations to make
// all array Elements equal
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find minimum number of operationsto make all
// array Elements equal
int countMinimumMoves(int arr[], int n, int k)
{
    int i;
    // Check if it is possible or not i.e., if all the
    // elements from index K to N are not equal
    for (i = k - 1; i < n; i++)
        if (arr[i] != arr[k - 1])
            return -1;
    // Find minimum number of moves
    for (i = k - 1; i >= 0; i--)
        if (arr[i] != arr[k - 1])
            return i + 1;
    // Elements are already equal
    return 0;
}
 
// Driver Code
int main()
{
    int arr[] = { 1, 2, 3, 4 };
    int K = 4;
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << countMinimumMoves(arr, n, K);
    return 0;
}
 
// This code is contributed by Sania Kumari Gupta

// C Program to find minimum number of operations to make
// all array Elements equal
 
#include <stdio.h>
 
// Function to find minimum number of operations to make all
// array Elements equal
int countMinimumMoves(int arr[], int n, int k)
{
    int i;
    // Check if it is possible or not i.e., if all the
    // elements from index K to N are not equal
    for (i = k - 1; i < n; i++)
        if (arr[i] != arr[k - 1])
            return -1;
    // Find minimum number of moves
    for (i = k - 1; i >= 0; i--)
        if (arr[i] != arr[k - 1])
            return i + 1;
    // Elements are already equal
    return 0;
}
 
// Driver Code
int main()
{
    int arr[] = { 1, 2, 3, 4 };
    int K = 4;
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("%d", countMinimumMoves(arr, n, K));
    return 0;
}
 
// This code is contributed by Sania Kumari Gupta

// Java Program to find minimum number of operations to make
// all array Elements equal
 
import java.io.*;
 
class GFG {
    // Function to find minimum number of operations to make
    // all array Elements equal
    static int countMinimumMoves(int arr[], int n, int k)
    {
        int i;
        // Check if it is possible or not i.e., if all the
        // elements from index K to N are not equal
        for (i = k - 1; i < n; i++)
            if (arr[i] != arr[k - 1])
                return -1;
        // Find minimum number of moves
        for (i = k - 1; i >= 0; i--)
            if (arr[i] != arr[k - 1])
                return i + 1;
        // Elements are already equal
        return 0;
    }
 
    // Driver Code
 
    public static void main(String[] args)
    {
        int arr[] = { 1, 2, 3, 4 };
        int K = 4;
        int n = arr.length;
        System.out.print(countMinimumMoves(arr, n, K));
    }
}
 
// This code is contributed by Sania Kumari Gupta

# Python3 Program to find minimum
# number of operations to make all
# array Elements equal
 
# Function to find minimum number
# of operations to make all array
# Elements equal
def countMinimumMoves(arr, n, k) :
 
    # Check if it is possible or not
    # That is if all the elements from
    # index K to N are not equal
    for i in range(k - 1, n) :
        if (arr[i] != arr[k - 1]) :
            return -1
 
    # Find minimum number of moves
    for i in range(k - 1, -1, -1) :
        if (arr[i] != arr[k - 1]) :
            return i + 1
 
    # Elements are already equal
    return 0
 
# Driver Code
if __name__ == "__main__" :
 
    arr = [ 1, 2, 3, 4 ]
    K = 4
 
    n = len(arr)
 
    print(countMinimumMoves(arr, n, K))
 
# This code is contributed by Ryuga

// C# Program to find minimum number of
// operations to make all array Elements
// equal
using System;
 
class GFG
{
     
// Function to find minimum number
// of operations to make all array
// Elements equal
static int countMinimumMoves(int []arr,
                             int n, int k)
{
    int i;
 
    // Check if it is possible or not
    // That is if all the elements from
    // index K to N are not equal
    for (i = k - 1; i < n; i++)
        if (arr[i] != arr[k - 1])
            return -1;
 
    // Find minimum number of moves
    for (i = k - 1; i >= 0; i--)
        if (arr[i] != arr[k - 1])
            return i + 1;
 
    // Elements are already equal
    return 0;
}
 
// Driver Code
public static void Main ()
{
    int []arr = { 1, 2, 3, 4 };
    int K = 4;
     
    int n = arr.Length;
     
    Console.Write(countMinimumMoves(arr, n, K));
}
}
 
// This code is contributed
// by 29AjayKumar

<?php
// PHP Program to find minimum number of
// operations to make all array Elements
// equal
 
// Function to find minimum number
// of operations to make all array
// Elements equal
function countMinimumMoves($arr, $n, $k)
{
 
    // Check if it is possible or not
    // That is if all the elements from
    // index K to N are not equal
    for ($i = $k - 1; $i < $n; $i++)
        if ($arr[$i] != $arr[$k - 1])
            return -1;
 
    // Find minimum number of moves
    for ($i = $k - 1; $i >= 0; $i--)
        if ($arr[$i] != $arr[$k - 1])
            return $i + 1;
 
    // Elements are already equal
    return 0;
}
 
// Driver Code
$arr = array(1, 2, 3, 4);
$K = 4;
 
$n = sizeof($arr);
 
echo countMinimumMoves($arr, $n, $K);
 
// This code is contributed
// by Akanksha Rai
?>

<script>
 
// JavaScript Program to find minimum number of
// operations to make all array Elements
// equal
 
 
// Function to find minimum number of operations
// to make all array Elements equal
function countMinimumMoves(arr, n, k)
{
    let i;
 
    // Check if it is possible or not
    // That is if all the elements from
    // index K to N are not equal
    for (i = k - 1; i < n; i++)
        if (arr[i] != arr[k - 1])
            return -1;
 
    // Find minimum number of moves
    for (i = k - 1; i >= 0; i--)
        if (arr[i] != arr[k - 1])
            return i + 1;
 
    // Elements are already equal
    return 0;
}
 
// Driver Code
    let arr = [ 1, 2, 3, 4 ];
    let K = 4;
 
    let n = arr.length;
 
    document.write(countMinimumMoves(arr, n, K));
 
 
 
// This code is contributed by Surbhi Tyagi.
 
</script>

3

Complejidad temporal: O(N)
Espacio auxiliar: O(1)