Dada una array arr[] de enteros y un entero K , podemos realizar la operación Bitwise OR 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: arr[] = {1, 9, 4, 3}, K = 3
Salida: 1
Podemos O a[0] con x, lo que hace que sea 3, que es igual a a[3]
Entrada: arr[] = {13, 26, 21, 15}, K = 13
Salida: -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 realices (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 contiene 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 return the count of // 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 OR 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 OR 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 OR operations return -1; } // Driver code int main() { int K = 3; int a[] = { 1, 9, 4, 3 }; 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.HashMap; class GFG { // Function to return the count of // 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 if (map.containsKey(a[i])) return 0; map.put(a[i], true); } // Create new array with OR 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.put(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.put(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, 9, 4, 3 }; int n = a.length; System.out.println(minOperations(a, n, K)); } } // This code is contributed by // sanjeev2552
Python3
# Python3 implementation of the approach # Function to return the count of # minimum operations required def minOperations(a, n, K) : map = dict.fromkeys(a,0) ; for i in range(n) : # Check if the initial array # already contains an equal pair if (map[a[i]]) : return 0; map[a[i]] = True; # Create new array with OR operations b = [0]*n; for i in range(n) : b[i] = a[i] | K; # Clear the map map.clear(); # Check if the solution # is a single operation for i in range(n) : # If Bitwise OR 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(n) : # Single operation # will be enough if a[i] not in map : pass elif (map[a[i]]) : return 1; # Clear the map map.clear(); # Check if the solution # is two operations for i in range(n) : # 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 OR operations return -1; # Driver code if __name__ == "__main__" : K = 3; a = [ 1, 9, 4, 3 ]; n = len(a); # Function call to compute the result print(minOperations(a, n, K)); # This code is contributed by AnkitRai01
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 OR 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, 9, 4, 3 }; int n = a.Length; Console.WriteLine(minOperations(a, n, K)); } } // This code is contributed by 29AjayKumar
Javascript
<script> // JavaScript implementation of the approach // Function to return the count of // minimum operations required function minOperations(a, n, K) { let map = new Map(); for (let i = 0; i < n; i++) { // Check if the initial array // already contains an equal pair if (map.has(a[i])) return 0; map.set(a[i], true); } // Create new array with OR operations let b = new Array(n); for (let i = 0; i < n; i++) b[i] = a[i] | K; // Clear the map map.clear(); // Check if the solution // is a single operation for (let 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.set(b[i], true); } // Check if any of the a[i] // gets equal to any other element // of the array after the operation for (let i = 0; i < n; i++) // Single operation // will be enough if (map.has(a[i])) return 1; // Clear the map map.clear(); // Check if the solution // is two operations for (let i = 0; i < n; i++) { // Check if the array 'b' // contains duplicates if (map.has(b[i])) return 2; map.set(b[i], true); } // Otherwise it is impossible to // create such an array with // Bitwise OR operations return -1; } // Driver code let K = 3; let a = [1, 9, 4, 3]; let n = a.length; // Function call to compute the result document.write(minOperations(a, n, K)); // This code is contributed by gfgking </script>
1
Complejidad de tiempo: O(n)
Espacio Auxiliar: O(n)