Given an array of N elements, the task is to find the minimum value of K such that Bitwise XOR of K with all array elements produces the same set of elements. If it is impossible to find any value of K then print “-1”.
Examples:
Input: arr[] = { 1, 0, 2, 3}
Output: 1
Explanation:
For K = 1,
1 xor 1 = 0
1 xor 0 = 1
1 xor 2 = 3
1 xor 3 = 2
Thus, K = 1 is the least possible positive value which leaves the array unaltered.Input: arr[] = { 7, 1, 2, 3, 8}
Output: -1
Naive Approach: The naive approach is to iterate for all the possible values of K in the range [1, 1024] and check if Bitwise XOR of K with all the elements in the array gives the same array elements or not. If for any minimum value of K the Bitwise XOR produces the same array then print that value of K else print “-1”.
Time Complexity: O(K*N2)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized by using additional space. Below are the steps:
- Insert all the elements into the set.
- Iterate for all possible values of K in the range [0, 1024].
- For every element in the set, find its Bitwise XOR with K.
- The first value of K for which all the elements generated after Bitwise XOR with the element inset is the same as that of the given set, then print the value of K.
- If no such K is obtained, print “-1”.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the minimum // value of K in given range int min_value( int arr[], int N) { int x, X, K; // Declare a set set< int > S; for ( int i = 0; i < N; i++) { S.insert(arr[i]); } // Initialize count variable int count = 0; // Iterate in range [1, 1024] for ( int i = 1; i <= 1024; i++) { // counter set as 0 count = 0; // Iterating through the Set for ( auto it = S.begin(); it != S.end(); it++) // Check if the XOR // calculated is present // in the Set { X = ((i | *it) - (i & *it)); // If the value of Bitwise XOR // inside the given set then // increment count if (S.find(X) != S.end()) { count++; } } // Check if the value of count is // equal to the size of set if (count == S.size()) { K = i; // Return minimum value of K return K; } } // If no such K is found return -1; } // Driver Code int main() { // Given array int arr[] = { 1, 0, 3, 3, 0, 2 }; int N = sizeof (arr) / sizeof (arr[0]); // Function Call cout << min_value(arr, N); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG { // Function to find the minimum // value of K in given range static int min_value( int arr[], int N) { int x, X, K; // Declare a set HashSet<Integer> S = new HashSet<Integer>(); for ( int i = 0 ; i < N; i++) { S.add(arr[i]); } // Initialize count variable int count = 0 ; // Iterate in range [1, 1024] for ( int i = 1 ; i <= 1024 ; i++) { // counter set as 0 count = 0 ; // Iterating through the Set for ( int it : S) { // Check if the XOR // calculated is present // in the Set X = ((i | it) - (i & it)); // If the value of Bitwise XOR // inside the given set then // increment count if (S.contains(X)) { count++; } } // Check if the value of count is // equal to the size of set if (count == S.size()) { K = i; // Return minimum value of K return K; } } // If no such K is found return - 1 ; } // Driver Code public static void main(String[] args) { // Given array int arr[] = { 1 , 0 , 3 , 3 , 0 , 2 }; int N = arr.length; // Function Call System.out.print(min_value(arr, N)); } } // This code is contributed by Rajput-Ji |
Python3
# Python3 program for the above approach # Function to find the minimum # value of K in given range def min_value(arr, N): x, X, K = 0 , 0 , 0 # Declare a set S = set () for i in range (N): S.add(arr[i]) # Initialize count variable count = 0 # Iterate in range [1, 1024] for i in range ( 1 , 1024 ): # counter set as 0 count = 0 # Iterating through the Set for it in S: # Check if the XOR # calculated is present # in the Set X = ((i | it) - (i & it)) # If the value of Bitwise XOR # inside the given set then # increment count if X in S: count + = 1 # Check if the value of count is # equal to the size of set if (count = = len (S)): K = i # Return minimum value of K return K # If no such K is found return - 1 # Driver Code # Given array arr = [ 1 , 0 , 3 , 3 , 0 , 2 ] N = len (arr) # Function Call print (min_value(arr, N)) # This code is contributed by shubhamsingh10 |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG { // Function to find the minimum // value of K in given range static int min_value( int [] arr, int N) { // int x; int X, K; // Declare a set HashSet< int > S = new HashSet< int >(); for ( int i = 0; i < N; i++) { S.Add(arr[i]); } // Initialize count variable int count = 0; // Iterate in range [1, 1024] for ( int i = 1; i <= 1024; i++) { // counter set as 0 count = 0; // Iterating through the Set foreach ( int it in S) { // Check if the XOR // calculated is present // in the Set X = ((i | it) - (i & it)); // If the value of Bitwise XOR // inside the given set then // increment count if (S.Contains(X)) { count++; } } // Check if the value of count is // equal to the size of set if (count == S.Count) { K = i; // Return minimum value of K return K; } } // If no such K is found return -1; } // Driver code static void Main() { // Given array int [] arr = { 1, 0, 3, 3, 0, 2 }; int N = arr.Length; // Function call Console.Write(min_value(arr, N)); } } // This code is contributed by divyeshrabadiya07 |
Javascript
<script> // Javascript implementation for the above approach // Function to find the minimum // value of K in given range function min_value(arr, N) { let x, X, K; // Declare a set let S = []; for (let i = 0; i < N; i++) { S.push(arr[i]); } // Initialize count variable let count = 0; // Iterate in range [1, 1024] for (let i = 1; i <= 1024; i++) { // counter set as 0 count = 0; // Iterating through the Set for (let it in S) { // Check if the XOR // calculated is present // in the Set X = ((i | it) - (i & it)); // If the value of Bitwise XOR // inside the given set then // increment count for (let j in S) { if (S[j]==X) { count++; } } } // Check if the value of count is // equal to the size of set if (count == S.length) { K = i; // Return minimum value of K return K; } } // If no such K is found return -1; } // Driver Code // Given array let arr = [ 1, 0, 3, 3, 0, 2 ]; let N = arr.length; // Function Call document.write(min_value(arr, N)); </script> |
1
Time Complexity: O(K*N*log2N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!