Dada una array A [] de N enteros y un entero K , la tarea es encontrar el número mínimo de reemplazos de elementos de la array necesarios para que el AND bit a bit de todos los elementos de la array sea estrictamente mayor que K .
Ejemplos:
Entrada: N = 4, K = 2, A[] = {3, 1, 2, 7}
Salida: 2
Explicación: Cambie A[1] = 3 y A[2] = 11.
Después de realizar dos operaciones: Array modificada : {3, 3, 11, 7}
Ahora, Bitwise AND de todos los elementos es 3 & 3 & 11 & 7 = 3Entrada: N = 3, K = 1, A[] = {2, 2, 2}
Salida: 0
Enfoque: este problema se puede resolver utilizando la manipulación de bits según la siguiente idea:
Encuentre la representación de bits del valor K. Para cada bit, suponga que está establecido y calcule cuántos reemplazos se requieren para lograr ese valor como AND bit a bit de los elementos de la array. El mínimo entre estos valores es la respuesta requerida.
Siga los pasos a continuación para implementar la observación anterior:
- Cree una variable de máscara con 32 bits e inicialícela a cero.
- A partir del 31.er bit más significativo, siga comprobando si el i -ésimo bit en K está activado o no.
- Si el i-ésimo bit está configurado, configure también ese bit en la máscara.
- Si el bit no está configurado, cree una variable temporal (por ejemplo, temp ) que tenga el valor de máscara pero que tenga el i -ésimo bit configurado para que el AND bit a bit de la array pueda ser estrictamente mayor que K.
- Para cada elemento de la array, compruebe si el AND bit a bit del elemento y temp es igual a temp .
- Si es temporal , entonces no hay necesidad de cambiar este elemento de la array.
- Encuentre el número de reemplazos (por ejemplo, X ) restando el número de elementos que no requieren cambio de N (el tamaño de la array).
- El valor mínimo de X entre todas las iteraciones desde el bit 31 hasta el bit 0 es la respuesta.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the
// minimum number of replacements
int count(int N, vector<int> A, int K)
{
// Initially assuming we need to change
// all elements of the array
int ans = N;
// Initialize mask as 0
int mask = 0;
// Starting from 31st bit check all
// the bits of X if they are set or not
for (int i = 31; i >= 0; i--) {
// If bit is set,
// set that bit in mask also
if ((K >> i) & 1)
mask |= (1 << i);
// If bit is not set then
// count the elements of array
// requiring no change
// and change answer to
// minimum replacements.
else {
int good = 0;
int temp = mask | (1 << i);
for (auto element : A)
if ((element & temp) == temp)
good++;
ans = min(ans, N - good);
}
}
return ans;
}
// Driver code
int main()
{
int N = 4, K = 2;
vector<int> A = { 3, 1, 2, 7 };
// Function call
int ans = count(N, A, K);
cout << ans << endl;
return 0;
}
C
// C code to implement the approach
#include<stdio.h>
#include<math.h>
int min(int a,int b)
{
return a<b?a:b;
}
// Function to find the minimum number of replacements
int count(int N, int A[], int K)
{
// Initially assuming we need to change all elements of the array
int ans = N;
// Initialize mask as 0
int mask = 0;
// Starting from 31st bit check all the bits of X if they are set or not
for (int i = 31; i >= 0; i--) {
// If bit is set, set that bit in mask also
if ((K >> i) & 1)
mask |= (1 << i);
// If bit is not set then count the elements of array requiring no change and change answer to minimum replacements.
else {
int good = 0;
int temp = mask | (1 << i);
for (int i=0;i<N;i++)
if ((A[i] & temp) == temp)
good++;
ans = min(ans, N - good);
}
}
return ans;
}
// Driver code
int main()
{
int N = 4, K = 2;
int A[] = {3,1,2,7};
// Function call
int ans = count(N, A, K);
printf("Ans : %d",ans);
return 0;
}
//This code is contributed by ashishsingh13122000
Java
// Java code to implement the approach
import java.io.*;
class GFG {
// Function to find the
// minimum number of replacements
static int count(int N, int[] A, int K)
{
// Initially assuming we need to change
// all elements of the array
int ans = N;
// Initialize mask as 0
int mask = 0;
// Starting from 31st bit check all
// the bits of X if they are set or not
for (int i = 31; i >= 0; i--) {
// If bit is set,
// set that bit in mask also
if (((K >> i) & 1) != 0)
mask |= (1 << i);
// If bit is not set then
// count the elements of array
// requiring no change
// and change answer to
// minimum replacements.
else {
int good = 0;
int temp = mask | (1 << i);
for( int element : A)
if ((element & temp) == temp) good++;
ans = Math.min(ans, N - good);
}
}
return ans;
}
// Driver code
public static void main (String[] args) {
int N = 4, K = 2;
int A[] = { 3, 1, 2, 7 };
// Function call
int ans = count(N, A, K);
System.out.println(ans);
}
}
// This code is contributed by hrithikgarg03188.
Python
# Python code to implement the approach # Function to find the # minimum number of replacements def count(N, A, K): # Initially assuming we need to change # all elements of the array ans = N # Initialize mask as 0 mask = 0 # Starting from 31st bit check all # the bits of X if they are set or not i = 31 while(i >= 0): # If bit is set, # set that bit in mask also if ((K >> i) & 1): mask |= (1 << i) # If bit is not set then # count the elements of array # requiring no change # and change answer to # minimum replacements. else: good = 0 temp = mask | (1 << i) for x in range(0, len(A)): if ((A[x] & temp) == temp): good += 1 ans = min(ans, N - good) i -= 1 return ans # Driver code N = 4 K = 2 A = [3, 1, 2, 7] # Function call ans = count(N, A, K) print(ans) # This code is contributed by Samim Hossain Mondal.
C#
// C# code to implement the approach
using System;
class GFG {
// Function to find the
// minimum number of replacements
static int count(int N, int[] A, int K)
{
// Initially assuming we need to change
// all elements of the array
int ans = N;
// Initialize mask as 0
int mask = 0;
// Starting from 31st bit check all
// the bits of X if they are set or not
for (int i = 31; i >= 0; i--) {
// If bit is set,
// set that bit in mask also
if (((K >> i) & 1) != 0)
mask |= (1 << i);
// If bit is not set then
// count the elements of array
// requiring no change
// and change answer to
// minimum replacements.
else {
int good = 0;
int temp = mask | (1 << i);
foreach(
int element in A) if ((element & temp)
== temp) good++;
ans = Math.Min(ans, N - good);
}
}
return ans;
}
// Driver code
public static void Main()
{
int N = 4, K = 2;
int[] A = { 3, 1, 2, 7 };
// Function call
int ans = count(N, A, K);
Console.WriteLine(ans);
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// JavaScript code for the above approach
// Function to find the
// minimum number of replacements
function count(N, A, K) {
// Initially assuming we need to change
// all elements of the array
let ans = N;
// Initialize mask as 0
let mask = 0;
// Starting from 31st bit check all
// the bits of X if they are set or not
for (let i = 31; i >= 0; i--) {
// If bit is set,
// set that bit in mask also
if ((K >> i) & 1)
mask |= (1 << i);
// If bit is not set then
// count the elements of array
// requiring no change
// and change answer to
// minimum replacements.
else {
let good = 0;
let temp = mask | (1 << i);
for (let element of A)
if ((element & temp) == temp)
good++;
ans = Math.min(ans, N - good);
}
}
return ans;
}
// Driver code
let N = 4, K = 2;
let A = [3, 1, 2, 7];
// Function call
let ans = count(N, A, K);
document.write(ans + '<br>')
// This code is contributed by Potta Lokesh
</script>
Producción:
2
Complejidad de tiempo: O(N * LogM) donde M es el elemento máximo de la array.
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por ishankhandelwals y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA