Given an array arr[] of integers of size N and an integer K. One can perform the Bitwise XOR operation between any array element and K any number of times. The task is to print the minimum number of such operations required to make any two elements of the array equal. If it is not possible to make any two elements of the array equal after performing the above-mentioned operation then print -1.
Examples:
Input : arr[] = {1, 9, 4, 3}, K = 3
Output :-1
Explanation : No possible to make any two elements equal
Input : arr[] = {13, 13, 21, 15}, K = 13
Output :0
Explanation : Already exists two same elements
Approach: The key observation is that if it is possible to make the desired array then the answer will be either 0, 1 or 2. It will never exceed 2.
Because, if (x ^ k) = y
then, performing (y ^ k) will give x again
- The answer will be 0, if there are already equal elements in the array.
- For the answer to be 1, we will create a new array b[] which holds b[i] = (a[i] ^ K),
Now, for each a[i] we will check if there is any index j such that i != j and a[i] = b[j].
If yes, then the answer will be 1. - For the answer to be 2, we will check for an index i in the new array b[], If there is any index j such that i != j and b[i] = b[j].
If yes, then the answer will be 2. - If any of the above conditions is not satisfied then the answer will be -1.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return the count of// minimum operations requiredint 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 XOR 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 XOR 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 XOR operations return -1;}// Driver codeint 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 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]) && map.get(a[i])) return 0; map.put(a[i], true); } // Create new array with XOR 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 XOR 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]) && map.get(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]) && map.get(b[i])) return 2; map.put(b[i], true); } // Otherwise it is impossible to // create such an array with // Bitwise XOR 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// Vivek Kumar Singh |
Python3
# Python3 implementation of the approach # Function to return the count of # minimum operations required def minOperations(a, n, K) : map = dict.fromkeys(a, False); 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 XOR 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 XOR 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] in map : 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 b[i] in map : return 2; map[b[i]] = True; # Otherwise it is impossible to # create such an array with # Bitwise XOR 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 XOR 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 Rajput-Ji |
Javascript
<script>// Javascript implementation of the approach// Function to return the count of// minimum operations requiredfunction 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[a[i]] = true; } // Create new array with XOR 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 XOR 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 (var i = 0; i < n; i++) // Single operation // will be enough if (map[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[b[i]]) return 2; map[b[i]] = true; } // Otherwise it is impossible to // create such an array with // Bitwise XOR operations return -1;}// Driver codevar K = 3;var a = [ 1, 9, 4, 3 ];var n = a.length;// Function call to compute the resultdocument.write( minOperations(a, n, K));</script> |
Output:
-1
Time complexity: O(n) where n is size of input array
Auxiliary space: O(n)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
