Minimice los pasos para hacer que los elementos de la array sean iguales eliminando el par adyacente e insertando OR bit a bit

Dada una array arr[] , que consta de N enteros, la tarea es encontrar el número mínimo de movimientos necesarios para que todos los números de la array resultante sean iguales. En un movimiento,  

• Tome dos números adyacentes arr[i] y arr[i+1] y elimínelos. 
• Inserte el OR bit a bit de arr[i] y arr[i+1] en la posición eliminada. 

Ejemplos :

Entrada : arr[] = {1, 1, 1, 0, 1}
Salida : 1
Explicación : después de la operación OR en arr[2] y arr[3] obtenemos, 1 | 0 = 1. 
Dado que la array arr[] se convierte en {1, 1, 1, 1} y aquí todos los elementos son iguales. 
Por lo tanto, solo se necesita 1 movimiento para hacer que todos los números sean iguales.

Entrada : arr[] = {1, 2, 3}
Salida : 1
Explicación : después de la operación OR en arr[0] y arr[1] obtenemos, 1 | 2 = 3. 
Ahora, el arreglo arr[] se convierte en {3, 3} y aquí ambos elementos son iguales. 
Por lo tanto, solo se necesita 1 movimiento para hacer que todos los números sean iguales.

Enfoque : El problema se puede resolver en base a la siguiente observación de las propiedades bit a bit:

Se sabe que x | x = x, [donde ‘|’ significa bit a bit O]. 

Digamos que la array tiene todos los elementos como X al final y un total de M elementos.
En base a esto, podemos suponer que había M subarreglos tales que los OR bit a bit de los elementos del subarreglo son X.

Cuanto más se acerca el valor de M a N, menos operaciones se realizan.
Entonces, la tarea se reduce a encontrar el número máximo de subarreglo tal que tienen OR = X bit a bit

Si hay M tales subarreglos, entonces el número de operaciones realizadas = N – M (porque en cada paso el tamaño se reduce en 1)

Siga los pasos a continuación para resolver el problema:

• Encuentre OR bit a bit de todos los elementos de la array y guárdelo (por ejemplo, Total_Or ).
• Inicialice una variable (digamos Group = 0 ) para contar cuántos subarreglos tienen el valor OR de Total_Or .
• Ejecute un ciclo en la array de i = 0 a N:
  • Calcule el OR bit a bit de los elementos (por ejemplo, Current_Or ).
  • Si Current_Or es lo mismo que Total_Or , Incremente el grupo en 1 y establezca Current_Or = 0 ;
• Después de ejecutar el bucle, devuelve N – Group .

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 return minimum number of moves
int findMinMoves(int* arr, int n)
{
    // Initialize the variables
    int Total_Or = 0;
    int Current_Or = 0;
    int Group = 0;
 
    // Find or of all array elements
    for (int i = 0; i < n; i++) {
        Total_Or |= arr[i];
    }
 
    // Find number of groups forming or
    // equal to Total_Or
    for (int i = 0; i < n; i++) {
        Current_Or |= arr[i];
 
        // If Current_Or = Total_Or,
        // increment Group by 1
        if (Current_Or == Total_Or) {
            Group++;
 
            // Reset Current_Or
            Current_Or = 0;
        }
    }
 
    // Return minimum number of moves
    return n - Group;
}
 
// Driver Code
int main()
{
    int arr[] = { 1, 1, 1, 0, 1 };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function call
    cout << findMinMoves(arr, N);
    return 0;
}

/*package whatever //do not write package name here */
import java.io.*;
 
class GFG
{
 
  // Java code to implement the above approach
 
  // Function to return minimum number of moves
  static int findMinMoves(int arr[], int n)
  {
    // Initialize the variables
    int Total_Or = 0;
    int Current_Or = 0;
    int Group = 0;
 
    // Find or of all array elements
    for (int i = 0; i < n; i++) {
      Total_Or |= arr[i];
    }
 
    // Find number of groups forming or
    // equal to Total_Or
    for (int i = 0; i < n; i++) {
      Current_Or |= arr[i];
 
      // If Current_Or = Total_Or,
      // increment Group by 1
      if (Current_Or == Total_Or) {
        Group++;
 
        // Reset Current_Or
        Current_Or = 0;
      }
    }
 
    // Return minimum number of moves
    return n - Group;
  }
 
  // Driver Code
  public static void main(String args[])
  {
    int arr[] = { 1, 1, 1, 0, 1 };
    int N = arr.length;
 
    // Function call
    System.out.println(findMinMoves(arr, N));
  }
}
 
// This code is contributed by shinjanpatra

# Python3 code to implement the above approach
# Function to return minimum number of moves
def findMinMoves(arr,n):
   
    # Initialize the variables
    Total_Or = 0;
    Current_Or = 0;
    Group = 0;
 
    # Find or of all array elements
    for i in range(0,n):
        Total_Or = Total_Or|arr[i]
 
    # Find number of groups forming or
    # equal to Total_Or
    for i in range(0,n):
        Current_Or |= arr[i]
 
        # If Current_Or = Total_Or,
        # increment Group by 1
        if (Current_Or == Total_Or):
            Group=Group+1
 
            # Reset Current_Or
            Current_Or = 0
    # Return minimum number of moves
    return n - Group
 
# Driver Code
N = 5
arr = [ 1, 1, 1, 0, 1 ]
 
# Function call
print(findMinMoves(arr, N))
 
# This code is contributed by akashish__

using System;
 
public class GFG{
 
  // Function to return minimum number of moves
  static int findMinMoves(int[] arr, int n)
  {
     
    // Initialize the variables
    int Total_Or = 0;
    int Current_Or = 0;
    int Group = 0;
 
    // Find or of all array elements
    for (int i = 0; i < n; i++) {
      Total_Or |= arr[i];
    }
 
    // Find number of groups forming or
    // equal to Total_Or
    for (int i = 0; i < n; i++) {
      Current_Or |= arr[i];
 
      // If Current_Or = Total_Or,
      // increment Group by 1
      if (Current_Or == Total_Or) {
        Group++;
 
        // Reset Current_Or
        Current_Or = 0;
      }
    }
 
    // Return minimum number of moves
    return n - Group;
  }
 
  public static void Main ()
  {
 
    // Code
    int N = 5;
    int[] arr = { 1, 1, 1, 0, 1 };
 
    // Function call
    int ans = findMinMoves(arr, N);
    Console.WriteLine(ans); 
  }
}
 
// This code is contributed by akashish__

<script>
       // JavaScript code for the above approach
 
       // Function to return minimum number of moves
       function findMinMoves(arr, n) {
           // Initialize the variables
           let Total_Or = 0;
           let Current_Or = 0;
           let Group = 0;
 
           // Find or of all array elements
           for (let i = 0; i < n; i++) {
               Total_Or |= arr[i];
           }
 
           // Find number of groups forming or
           // equal to Total_Or
           for (let i = 0; i < n; i++) {
               Current_Or |= arr[i];
 
               // If Current_Or = Total_Or,
               // increment Group by 1
               if (Current_Or == Total_Or) {
                   Group++;
 
                   // Reset Current_Or
                   Current_Or = 0;
               }
           }
 
           // Return minimum number of moves
           return n - Group;
       }
 
       // Driver Code
 
       let arr = [1, 1, 1, 0, 1];
       let N = arr.length;
 
       // Function call
       document.write(findMinMoves(arr, N));
 
 
   // This code is contributed by Potta Lokesh
   </script>

1

Complejidad de Tiempo : O(N)
Espacio Auxiliar : O(1)