Given an array arr[] of odd length N containing positive integers. The task is to find a positive integer X such that, adding X to all the elements of arr[] and then taking XOR of all the elements gives 0. Return -1 if no such X exists.
Examples:
Input: arr[] = {2, 4, 5}
Output: 1
Explanation: Following are the operations performed in arr[] to get the desired result.
Adding 1 to each element in arr[] updates arr[] to arr[] = {3, 5, 6}
Now XOR of all the elements in arr[] is 3^5^6 = 0.
Therefore, 1 is the required answer.Input: arr[] = {4, 5, 13}
Output: -1
Explanation: No such x exists for fulfilling the desired conditions.
Approach: XOR of Odd number of 1’s = 1, while even number of 1’s = 0. This idea can be used to solve the given problem. Follow the steps mentioned below:
- Initialize variable X = 0.
- The binary representations of the array elements will be used for traversal of the elements and determining X.
- Start traversing from the 0th bit to 63rd bit.
- If at any bit position total number of set bits (1’s) of the array elements are odd, add that power of 2 with X.
- If after completion of iteration there is odd number of 1 at any bit position then no such X exists. Otherwise, print X as answer.
See the illustrations below:
Illustration:
Case-1 (X possible): Take arr[] = { 2, 4, 5}
5th 4th 3rd 2nd 1st 0th arr[0] 0 0 0 0 1 0 arr[1] 0 0 0 1 0 0 arr[2] 0 0 0 1 0 1 X 0 0 0 0 0 0
- Initially, X = 0 0 0 0 0 0, at 0th position set(1) bits are odd, so in order to make the set bits even, flip the bits at 0th position. So, for flipping the bits just add (0 0 0 0 0 1) to all the elements of arr[] and in X.
- Now, the table will look like the following:
5th 4th 3rd 2nd 1st 0th arr[0] 0 0 0 0 1 1 arr[1] 0 0 0 1 0 1 arr[2] 0 0 0 1 1 0 XOR 0 0 0 0 0 0 X 0 0 0 0 0 1
- Now, the XOR of (arr[0]+x) ^ ( arr[1]+x) ^ arr[2]+x) = 0, result will be 0. So, print res = X.
Take the following when no possible X
Case-2: Take example: arr[] = { 4, 5, 13 }
5th 4th 3rd 2nd 1st 0th arr[0] 0 0 0 1 0 0 arr[1] 0 0 0 1 0 1 arr[2] 0 0 1 1 0 1 XOR 0 0 1 1 0 0 X 0 0 0 0 0 0 XOR = Arr[0] ^ Arr[1] ^ Arr[2] = 1 1 0 0, Here there are odd number of 1‘s at 2nd and 3rd bits.
- So, add 2pow(2nd) to all elements of arr and in X, then again will take the XOR, after this the elements become:
5th 4th 3rd 2nd 1st 0th arr[0] 0 0 1 0 0 0 arr[1] 0 0 1 0 0 1 arr[2] 0 1 0 0 0 1 XOR 0 1 0 0 0 0 X 0 0 0 1 0 0 If this keeps on going the left most 1 in XOR keeps on moving left.
Below is the implementation of the above approach:
C++
// C++ program for above approach#include <bits/stdc++.h>using namespace std;// Function to find required resultlong long solve(vector<long long>& a, int n){ long long res = 0, j = 0, one = 1; // For 64 Bit while (j < 64) { // j is traversing each bit long long Xor = 0; long long powerOf2 = one << j; for (auto x : a) Xor ^= x; if (j == 63 && (Xor & powerOf2)) return -1; if (Xor & powerOf2) { res += powerOf2; for (int i = 0; i < n; i++) a[i] += powerOf2; } j++; } return res;}// Driver Codeint main(){ // Size of arr[] int N = 3; vector<long long> arr = { 2, 4, 5 }; cout << solve(arr, N) << '\n'; return 0;} |
Java
// Java program for above approachclass GFG{// Function to find required resultstatic long solve(int[] a, int n){ long res = 0, j = 0, one = 1; // For 64 Bit while (j < 64) { // j is traversing each bit long Xor = 0; long powerOf2 = one << j; for (int x : a) Xor ^= x; if (j == 63 && (Xor & powerOf2)!=0) return -1; if ((Xor & powerOf2)!=0) { res += powerOf2; for (int i = 0; i < n; i++) a[i] += powerOf2; } j++; } return res;}// Driver Codepublic static void main(String[] args){ // Size of arr[] int N = 3; int[] arr = { 2, 4, 5 }; System.out.print(solve(arr, N));}}// This code is contributed by shikhasingrajput |
Python3
# python program for above approach# Function to find required resultdef solve(a, n): res = 0 j = 0 one = 1 # For 64 Bit while (j < 64): # j is traversing each bit Xor = 0 powerOf2 = one << j for x in a: Xor ^= x if (j == 63 and (Xor & powerOf2)): return -1 if (Xor & powerOf2): res += powerOf2 for i in range(0, n): a[i] += powerOf2 j += 1 return res# Driver Codeif __name__ == "__main__": # Size of arr[] N = 3 arr = [2, 4, 5] print(solve(arr, N)) # This code is contributed by rakeshsahni |
C#
// C# program for above approachusing System;class GFG{ // Function to find required result static long solve(int[] a, int n) { int res = 0, j = 0, one = 1; // For 64 Bit while (j < 64) { // j is traversing each bit long Xor = 0; long powerOf2 = one << j; foreach (int x in a) Xor ^= x; if (j == 63 && (Xor & powerOf2) != 0) return -1; if ((Xor & powerOf2) != 0) { res += (int)powerOf2; for (int i = 0; i < n; i++) a[i] += (int)powerOf2; } j++; } return res; } // Driver Code public static void Main() { // Size of arr[] int N = 3; int[] arr = { 2, 4, 5 }; Console.Write(solve(arr, N)); }}// This code is contributed by gfgking |
Javascript
<script>// JavaScript program for above approach // Function to find required resultfunction solve(a, n){ let res = 0, j = 0, one = 1; // For 64 Bit while (j < 64) { // j is traversing each bit let Xor = 0; let powerOf2 = one << j; for(let x of a) Xor ^= x; if (j == 63 && (Xor & powerOf2)) return -1; if (Xor & powerOf2) { res += powerOf2; for(let i = 0; i < n; i++) a[i] += powerOf2; } j++; } return res;}// Driver Code// Size of arr[]let N = 3;let arr = [ 2, 4, 5 ];document.write(solve(arr, N) + '<br>');// This code is contributed by Potta Lokesh</script> |
1
Time Complexity: O(N*logN)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
