Dada una array arr[] de longitud N , la tarea es encontrar las operaciones mínimas para hacer que todos los elementos de la array sean iguales en cada operación:
- Elija cualquier valor K cualquier subarreglo de longitud par 2*K .
- Reemplace la mitad izquierda del subarreglo por la mitad derecha del subarreglo.
Ejemplos:
Entrada: arr[] = {4, 4, 4, 2, 4}
Salida: 1
Explicación: En la primera operación, elija el índice i = 3 y K = 1.
Entonces se elige un subarreglo de 2K de longitud de índices [3, 4].
Reemplace la primera mitad por la segunda mitad. Entonces se convierte en {4, 4, 4, 4, 4}Entrada: arr[] = {4, 2, 1, 3}
Salida: 2
Explicación: En la primera operación, elija el índice i = 2, K = 1.
La array se convierte en {4, 2, 3, 3}.
En la segunda operación, elija el índice 0 y K = 2.
Entonces, el subarreglo de longitud 4 y los dos primeros se reemplazan por los dos últimos.
Entonces la array se convierte en {3, 3, 3, 3}. Entonces las operaciones son 2.
Planteamiento: Este problema se puede resolver con base en la siguiente observación:
Observaciones:
El último elemento nunca se puede cambiar con algún otro elemento ya que no hay elementos a la derecha por lo que todos los elementos anteriores deben ser iguales al último elemento.
Para minimizar las operaciones, mantenga tantos elementos iguales en la mitad derecha del subarreglo como sea posible.
Siga los pasos mencionados a continuación para resolver el problema anterior:
- Inicialice una variable res = 0 para almacenar las operaciones requeridas
- Recorra desde el final de la array i = N – 2 a 0 :
- Comprobar si arr[i] es igual al último elemento
- Si es igual no se requiere operación
- De lo contrario, es necesario realizar una operación eligiendo algunos K y una array de longitud 2 * K y reemplazar la primera mitad con la segunda mitad.
- Considere arr[i] como el último elemento de la mitad izquierda y ( i+1 a N-1 ) como la mitad derecha y reemplace todos los elementos de la mitad izquierda con los elementos de la mitad derecha.
- Así que incremente la resolución y muévase al índice i = (i – (N – 1 – i)) para tener operaciones mínimas reemplazando la mitad entera por la segunda mitad.
- Devuelve la res como la respuesta requerida.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to count minimum operations
int min_ops(int arr[], int n)
{
int res = 0;
int i = n - 1;
while (i > 0) {
// Check if arr[i]== arr[n-1]
// If they are equal do i--
if (arr[i] == arr[n - 1]) {
i--;
}
else {
// Try to do an operation
// It is always optimal to
// to move to the index of
// length n-1-i before i
// since it is easy to replace
// first half with second half
res++;
// Move i to half of the
// elements after that
i -= (n - i - 1);
}
}
return res;
}
// Driver code
int main()
{
int arr[] = { 4, 2, 1, 3 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function call
cout << min_ops(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
class GFG {
// Function to count minimum operations
static int min_ops(int arr[], int n)
{
int res = 0;
int i = n - 1;
while (i > 0) {
// Check if arr[i]== arr[n-1]
// If they are equal do i--
if (arr[i] == arr[n - 1]) {
i--;
}
else {
// Try to do an operation
// It is always optimal to
// to move to the index of
// length n-1-i before i
// since it is easy to replace
// first half with second half
res++;
// Move i to half of the
// elements after that
i -= (n - i - 1);
}
}
return res;
}
// Driver code
public static void main (String[] args) {
int arr[] = { 4, 2, 1, 3 };
int N = arr.length;
// Function call
System.out.print(min_ops(arr, N));
}
}
// This code is contributed by hrithikgarg03188.
Python3
# Python program for the above approach # Function to count minimum operations def min_ops(arr, n): res = 0 i = n - 1 while (i > 0): # Check if arr[i]== arr[n-1] # If they are equal do i-- if (arr[i] == arr[n - 1]): i = i-1 else: # Try to do an operation # It is always optimal to # to move to the index of # length n-1-i before i # since it is easy to replace # first half with second half res = res + 1 # Move i to half of the # elements after that i = i - (n - i - 1) return res # Driver code arr = [4, 2, 1, 3] N = len(arr) # Function call print(min_ops(arr, N)) # This code is contributed by Taranpreet
C#
// C# program for the above approach
using System;
class GFG {
// Function to count minimum operations
static int min_ops(int[] arr, int n)
{
int res = 0;
int i = n - 1;
while (i > 0) {
// Check if arr[i]== arr[n-1]
// If they are equal do i--
if (arr[i] == arr[n - 1]) {
i--;
}
else {
// Try to do an operation
// It is always optimal to
// to move to the index of
// length n-1-i before i
// since it is easy to replace
// first half with second half
res++;
// Move i to half of the
// elements after that
i -= (n - i - 1);
}
}
return res;
}
// Driver code
public static void Main()
{
int[] arr = { 4, 2, 1, 3 };
int N = arr.Length;
// Function call
Console.Write(min_ops(arr, N));
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// JavaScript program for the above approach
// Function to count minimum operations
const min_ops = (arr, n) => {
let res = 0;
let i = n - 1;
while (i > 0) {
// Check if arr[i]== arr[n-1]
// If they are equal do i--
if (arr[i] == arr[n - 1]) {
i--;
}
else {
// Try to do an operation
// It is always optimal to
// to move to the index of
// length n-1-i before i
// since it is easy to replace
// first half with second half
res++;
// Move i to half of the
// elements after that
i -= (n - i - 1);
}
}
return res;
}
// Driver code
let arr = [4, 2, 1, 3];
let N = arr.length;
// Function call
document.write(min_ops(arr, N));
// This code is contributed by rakeshsahni
</script>
2
Complejidad de tiempo: O(N)
Complejidad de espacio: O(1)
Publicación traducida automáticamente
Artículo escrito por lokeshpotta20 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA