Dada una array A[] que tiene N enteros positivos, la tarea es encontrar el número mínimo de pasos para construir esta array a partir de una array inicial de tamaño N que tiene todos 0 s siguiendo las siguientes operaciones:
- Seleccione cualquier subsecuencia de la array.
- Suma cualquier potencia de 2 a cada elemento de la subsecuencia.
Ejemplos:
Entrada: A = {5, 5, 5}, N = 3
Salida: 2
Explicación: Inicialmente, A = {0, 0, 0}
Primero, agregue 4 (2 2 ) a todos los elementos de A.
A se convierte en {4, 4, 4}.
Luego, agregue 1 (2 0 ) a todos los elementos de A.
A ahora se convierte en {5, 5, 5}
Por lo tanto, se requirieron dos operaciones para igualar A2 y A1.Entrada: A1 = [5, 2, 1], N = 3
Salida: 3
Planteamiento: La solución al problema se basa en el siguiente concepto matemático:
Cada número se puede expresar como la suma de los exponentes de 2, es decir, la representación binaria.
Para obtener un número en pasos mínimos sumando potencias de 2 a 0, necesitamos sumar solo las potencias de los bits establecidos.
Para minimizar el paso de formación de la array, la opción óptima es seleccionar todos los elementos que tienen un bit en la misma posición a la vez y realizar la operación en todos ellos.Por lo tanto, el problema se reduce a encontrar el número total de posiciones de bits establecidas únicas en todos los elementos de la array .
Siga los pasos mencionados a continuación para implementar la idea:
- Como necesitamos los bits establecidos únicos entre todos los elementos de la array, debemos realizar el OR bit a bit de todos los elementos y contar los bits establecidos de ese valor.
- Inicialice una variable (por ejemplo, X ) para almacenar el OR bit a bit de todos los elementos de la array.
- Iterar a través de todos los elementos de la array:
- Realice la operación OR bit a bit con X .
- Calcule los bits establecidos en X .
- El conteo de bits establecidos es la respuesta requerida.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ code for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate the minimum steps
int minimumOperations(int A[],int n){
// Initially, bitwise Or is
// equal to first element of the array
int bitwiseOr = A[0];
// Calculating the bitwise OR
// with each element in the array
for(int i=1;i<n;i++)
bitwiseOr |= A[i];
// Calculating the number of set
// bits in the bitwise OR
int ans = __builtin_popcount(bitwiseOr);
// Return the number of set bits
// as the required answer
return ans;
}
// Driver Code
int main()
{
int A[]= {5, 2, 1};
int N = 3;
//Function Call
cout<<(minimumOperations(A, N));
}
// This code is contributed by Potta Lokesh
Java
// Java code for the above approach
public class GFG {
// recursive function to count set bits
public static int countSetBits(int n)
{
// base case
if (n == 0)
return 0;
else
// if last bit set add 1 else add 0
return (n & 1) + countSetBits(n >> 1);
}
// Function to calculate the minimum steps
static int minimumOperations(int A[],int n){
// Initially, bitwise Or is
// equal to first element of the array
int bitwiseOr = A[0];
// Calculating the bitwise OR
// with each element in the array
for(int i=1;i<n;i++)
bitwiseOr |= A[i];
// Calculating the number of set
// bits in the bitwise OR
int ans = countSetBits(bitwiseOr);
// Return the number of set bits
// as the required answer
return ans;
}
// Driver Code
public static void main (String[] args)
{
int A[]= {5, 2, 1};
int N = 3;
//Function Call
System.out.println(minimumOperations(A, N));
}
}
// This code is contributed by AnkThon
Python3
# Python3 code to implement the approach
# Function to calculate the minimum steps
def minimumOperations(A, n):
# Initially, bitwise Or is
# equal to first element of the array
bitwiseOr = A[0]
# Calculating the bitwise OR
# with each element in the array
for i in range(1, n):
bitwiseOr |= A[i]
# Calculating the number of set
# bits in the bitwise OR
ans = bin(bitwiseOr).count("1")
# Return the number of set bits
# as the required answer
return ans
#Driver Code
if __name__ == '__main__':
A = [5, 2, 1]
N = 3
#Function Call
print(minimumOperations(A, N))
C#
// C# program to implement above approach
using System;
using System.Collections;
using System.Collections.Generic;
class GFG
{
// recursive function to count set bits
static int countSetBits(int n)
{
// base case
if (n == 0)
return 0;
else
// if last bit set add 1 else add 0
return (n & 1) + countSetBits(n >> 1);
}
// Function to calculate the minimum steps
static int minimumOperations(int[] A, int n)
{
// Initially, bitwise Or is
// equal to first element of the array
int bitwiseOr = A[0];
// Calculating the bitwise OR
// with each element in the array
for(int i = 1 ; i < n ; i++){
bitwiseOr |= A[i];
}
// Calculating the number of set
// bits in the bitwise OR
int ans = countSetBits(bitwiseOr);
// Return the number of set bits
// as the required answer
return ans;
}
public static void Main(string[] args){
int[] A = new int[]{5, 2, 1};
int N = 3;
//Function Call
Console.WriteLine(minimumOperations(A, N));
}
}
// This code is contributed by entertain2022.
Javascript
<script>
// JavaScript code for the above approach
// recursive function to count set bits
function countSetBits(n)
{
// base case
if (n == 0)
return 0;
else
// if last bit set add 1 else add 0
return (n & 1) + countSetBits(n >> 1);
}
// Function to calculate the minimum steps
function minimumOperations(A,n){
// Initially, bitwise Or is
// equal to first element of the array
let bitwiseOr = A[0];
// Calculating the bitwise OR
// with each element in the array
for(let i=1;i<n;i++)
bitwiseOr |= A[i];
// Calculating the number of set
// bits in the bitwise OR
let ans = countSetBits(bitwiseOr);
// Return the number of set bits
// as the required answer
return ans;
}
// Driver Code
let A = [5, 2, 1];
let N = 3;
//Function Call
document.write(minimumOperations(A, N),"</br>");
// This code is contributed by shinjanpatra
</script>
3
Complejidad temporal: O(N)
Espacio auxiliar: O(1)