Dada una array de números enteros de tamaño ‘n’ y un número entero ‘k’,
podemos realizar la operación Bitwise AND entre cualquier elemento de la array y ‘k’ cualquier número de veces.
La tarea es imprimir el número mínimo de tales operaciones requeridas para hacer que dos elementos de la array sean iguales.
Si no es posible hacer que dos elementos de la array sean iguales después de realizar la operación mencionada anteriormente, imprima ‘-1’.
Ejemplos:
Entrada: k = 6; Array: 1, 2, 1, 2
Salida: 0
Explicación: Ya hay dos elementos iguales en la array, por lo que la respuesta es 0.
Entrada: k = 2; Array: 5, 6, 2, 4
Salida: 1
Explicación: si aplicamos la operación AND en el elemento ‘6’, se convertirá en 6 y 2 = 2
Y la array se convertirá en 5 2 2 4,
ahora, la array tiene dos elementos iguales, entonces la respuesta es 1.
Entrada: k = 15; Array: 1, 2, 3
Salida: -1
Explicación: No importa cuántas veces realicemos la operación mencionada anteriormente,
esta array nunca tendrá un par de elementos iguales. Entonces la respuesta es -1
Enfoque:
La observación clave es que si es posible hacer la array deseada, la respuesta será ‘0’, ‘1’ o ‘2’. Nunca excederá de ‘2’.
Porque, si (x&k) = y
entonces, no importa cuántas veces ejecutes (y&k)
siempre dará ‘y’ como resultado.
- La respuesta será ‘0’, si ya hay elementos iguales en la array.
- Para que la respuesta sea ‘1’, crearemos una nueva array b que contenga b[i] = (a[i]&K).
Ahora, para cada a[i] comprobaremos si hay algún índice ‘j’ tal que i!=j y a[i]=b[j].
Si es así, entonces la respuesta será ‘1’. - Para que la respuesta sea ‘2’, buscaremos un índice ‘i’ en la nueva array b,
si hay algún índice ‘j’ tal que i != j y b[i] = b[j].
Si es así, entonces la respuesta será ‘2’. - Si alguna de las condiciones anteriores no se cumple, la respuesta será ‘-1’.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to count the
// minimum operations required.
int minOperations(int a[], int n, int K)
{
unordered_map<int, bool> map;
for (int i = 0; i < n; i++) {
// check if the initial array
// already contains an equal pair
if (map[a[i]])
return 0;
map[a[i]] = true;
}
// create new array with AND operations
int b[n];
for (int i = 0; i < n; i++)
b[i] = a[i] & K;
// clear the map
map.clear();
// Check if the solution
// is a single operation
for (int i = 0; i < n; i++) {
// If Bitwise operation between
//'k' and a[i] gives
// a number other than a[i]
if (a[i] != b[i])
map[b[i]] = true;
}
// Check if any of the a[i]
// gets equal to any other element
// of the array after the operation.
for (int i = 0; i < n; i++)
// Single operation
// will be enough
if (map[a[i]])
return 1;
// clear the map
map.clear();
// Check if the solution
// is two operations
for (int i = 0; i < n; i++) {
// Check if the array 'b'
// contains duplicates
if (map[b[i]])
return 2;
map[b[i]] = true;
}
// otherwise it is impossible to
// create such an array with
// Bitwise AND operations
return -1;
}
// Driver code
int main()
{
int K = 3;
int a[] = { 1, 2, 3, 7 };
int n = sizeof(a)/sizeof(a[0]);
// Function call to compute the result
cout << minOperations(a, n, K);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class geeks
{
// Function to count the
// minimum operations required.
public static int minOperations(int[] a, int n, int K)
{
HashMap<Integer, Boolean> map = new HashMap<>();
for (int i = 0; i < n; i++)
{
// check if the initial array
// already contains an equal pair
// try-catch is used so that
// nullpointer exception can be handled
try
{
if (map.get(a[i]))
return 1;
}
catch (Exception e)
{
//TODO: handle exception
}
try
{
map.put(a[i], true);
} catch (Exception e) {}
}
// create new array with AND operations
int[] b = new int[n];
for (int i = 0; i < n; i++)
b[i] = a[i] & K;
// clear the map
map.clear();
// Check if the solution
// is a single operation
for (int i = 0; i < n; i++)
{
// If Bitwise operation between
// 'k' and a[i] gives
// a number other than a[i]
if (a[i] != b[i])
{
try
{
map.put(b[i], true);
}
catch (Exception e) {}
}
}
// Check if any of the a[i]
// gets equal to any other element
// of the array after the operation.
for (int i = 0; i < n; i++)
{
// Single operation
// will be enough
try
{
if (map.get(a[i]))
return 1;
}
catch (Exception e)
{
//TODO: handle exception
}
}
// clear the map
map.clear();
// Check if the solution
// is two operations
for (int i = 0; i < n; i++)
{
// Check if the array 'b'
// contains duplicates
try
{
if (map.get(b[i]))
return 2;
}
catch (Exception e)
{
//TODO: handle exception
}
try
{
map.put(b[i], true);
}
catch (Exception e)
{
//TODO: handle exception
}
}
// otherwise it is impossible to
// create such an array with
// Bitwise AND operations
return -1;
}
// Driver Code
public static void main(String[] args)
{
int K = 3;
int[] a = { 1, 2, 3, 7 };
int n = a.length;
// Function call to compute the result
System.out.println(minOperations(a, n, K));
}
}
// This code is contributed by
// sanjeev2552
Python3
# Python3 implementation of the approach from collections import defaultdict # Function to count the minimum # operations required. def minOperations(a, n, K): Map = defaultdict(lambda:False) for i in range(0, n): # check if the initial array # already contains an equal pair if Map[a[i]] == True: return 0 Map[a[i]] = True # create new array with AND operations b = [] for i in range(0, n): b.append(a[i] & K) # clear the map Map.clear() # Check if the solution # is a single operation for i in range(0, n): # If Bitwise operation between #'k' and a[i] gives # a number other than a[i] if a[i] != b[i]: Map[b[i]] = True # Check if any of the a[i] # gets equal to any other element # of the array after the operation. for i in range(0, n): # Single operation # will be enough if Map[a[i]] == True: return 1 # clear the map Map.clear() # Check if the solution # is two operations for i in range(0, n): # Check if the array 'b' # contains duplicates if Map[b[i]] == True: return 2 Map[b[i]] = True # otherwise it is impossible to # create such an array with # Bitwise AND operations return -1 # Driver code if __name__ == "__main__": K = 3 a = [1, 2, 3, 7] n = len(a) # Function call to compute the result print(minOperations(a, n, K)) # This code is contributed by Rituraj Jain
C#
// C# implementation of the approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to return the count of
// minimum operations required
public static int minOperations(int[] a,
int n, int K)
{
Dictionary<int, Boolean> map =
new Dictionary<int, Boolean>();
for (int i = 0; i < n; i++)
{
// Check if the initial array
// already contains an equal pair
if (map.ContainsKey(a[i]))
return 0;
map.Add(a[i], true);
}
// Create new array with AND operations
int[] b = new int[n];
for (int i = 0; i < n; i++)
b[i] = a[i] & K;
// Clear the map
map.Clear();
// Check if the solution
// is a single operation
for (int i = 0; i < n; i++)
{
// If Bitwise OR operation between
// 'k' and a[i] gives
// a number other than a[i]
if (a[i] != b[i])
map.Add(b[i], true);
}
// Check if any of the a[i]
// gets equal to any other element
// of the array after the operation
for (int i = 0; i < n; i++)
{
// Single operation
// will be enough
if (map.ContainsKey(a[i]))
return 1;
}
// Clear the map
map.Clear();
// Check if the solution
// is two operations
for (int i = 0; i < n; i++)
{
// Check if the array 'b'
// contains duplicates
if (map.ContainsKey(b[i]))
return 2;
map.Add(b[i], true);
}
// Otherwise it is impossible to
// create such an array with
// Bitwise OR operations
return -1;
}
// Driver code
public static void Main(String[] args)
{
int K = 3;
int[] a = { 1, 2, 3, 7 };
int n = a.Length;
Console.WriteLine(minOperations(a, n, K));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript implementation of the approach
// Function to count the
// minimum operations required.
function minOperations(a, n, K)
{
var map = new Map();
for (var i = 0; i < n; i++) {
// check if the initial array
// already contains an equal pair
if (map[a[i]])
return 0;
map.set(a[i], true);
}
// create new array with AND operations
var b = Array(n);
for (var i = 0; i < n; i++)
b[i] = a[i] & K;
// clear the map
map = new Map();
// Check if the solution
// is a single operation
for (var i = 0; i < n; i++) {
// If Bitwise operation between
//'k' and a[i] gives
// a number other than a[i]
if (a[i] != b[i])
map.set(b[i], true);
}
// Check if any of the a[i]
// gets equal to any other element
// of the array after the operation.
for (var i = 0; i < n; i++)
// Single operation
// will be enough
if (map.get(a[i]))
return 1;
// clear the map
map = new Map();
// Check if the solution
// is two operations
for (var i = 0; i < n; i++) {
// Check if the array 'b'
// contains duplicates
if (map.get(b[i]))
return 2;
map.set(b[i], true);
}
// otherwise it is impossible to
// create such an array with
// Bitwise AND operations
return -1;
}
// Driver code
var K = 3;
var a = [1, 2, 3, 7];
var n = a.length;
// Function call to compute the result
document.write( minOperations(a, n, K));
</script>
Producción:
1
Complejidad: O(n)