Find a Number X Such that XOR of Given Array after Adding X to Each Element is 0

Approach

You are given N non-negative integers, where N is odd. Find a positive integer x such that, after adding x to all the N elements, the xor of all the elements becomes zero. If no such non-negative integer exists, print -1.

We can solve this problem bit by bit. We know that the Bitwise xor of even number of ones is zero, and the bitwise xor of odd number of ones is one. 

Let x be the number of zeros at ith bit of given elements. Now there are two cases:

Case 1 (x is even): The number of ones at the ith bit is odd because N is odd, so if we flip ith bit of all the elements, then the number of ones becomes even, and the number of zeros becomes odd.

To flip the ith bit of all the given elements, add ith power of 2 to all the elements.

Case 2 (x is odd): The number of ones at the ith bit is even, so there is no need to flip the ith bit.

Step to solve:

1. Declare a variable 'ans' to store the final answer. Initialize it with zero.
2. Start iterating from the 0th bit to the 61st bit.
3. If the number of ones at the ith bit is odd, add ith power of 2 (1 << i) to every element. Also, add it to the answer.
4. Check if the xor of the final array is zero or not. If not, print -1. Else print ans.

Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int M = 1e6 + 1;

signed main(){
   ios::sync_with_stdio(false);
   cin.tie(0);
   //int tt; cin >> tt; while(tt--)
   {
       //size of array
       int N;
       cin >> N;
       //given array
       int a[N + 5] = {};
       for(int i = 1; i <= N; ++i)
           cin >> a[i];
       //to store final answer
       int ans = 0;
       //Start iterating from the 0th bit to the 61st bit.
       for(int bit = 0; bit < 62; ++bit){
           //to store the answers
           int one_count = 0;
           //ith power of 2
           int powerOf2 = ((int)1 << bit);
           for(int j = 1; j <= N; ++j){
               one_count += a[j] & powerOf2;
           }
           if(one_count%2 == 0)
               continue;
           //add ith power of 2 to final answer
           ans += powerOf2;
           //add ith power of 2 to every element
           for(int j = 1; j <= N; ++j){
               a[j] += powerOf2;
           }
       }
       //Check if the xor of the final array is zero or not
       int xr = 0;
       for(int i = 1; i <= N; ++i){
           xr = xr ^ a[i];
       }
       //if xor is zero, print -1
       if(xr != 0){
           cout << -1 << "\n";
       }
       //else print 0
       else{
           cout << ans << "\n";
       }
   }
   
   return 0;
}

Input 

3
5 3 1

Output

1

Dry run

Time Complexity

The time complexity is O(63 * N).

Space Complexity

The space complexity is O(1).

Also see, Euclid GCD Algorithm

FAQs

1. What is bitwise xor??
   For a bit position, the bitwise xor operator returns 1 if the number of set bits at that position is odd. Otherwise, it returns 0.
    
2. What is (1 << i)??
   '<<' is known as the left shift operator, and the expression (1 << i) is equivalent to ith power of 2.

Key Takeaways

In this article, we solved a problem on bit manipulation. If you are doing competitive programming, then bit manipulation is one of the most important topic for you. Check out this coding ninjas course to get a good grasp on it.

Check out this problem - XOR Queries On Tree

To learn more about such data structures and algorithms, Coding Ninjas Studio is a one-stop destination. This platform will help you to improve your coding techniques and give you an overview of interview experiences in various product-based companies by providing Online Mock Test Series and many more benefits.

Happy learning!