Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Problem Statement
2.
Sample Test Cases
3.
Approach
4.
Code
4.1.
Input 
4.2.
Output
5.
Dry run
6.
Time Complexity
7.
Space Complexity
8.
FAQs
9.
Key Takeaways
Last Updated: Mar 27, 2024

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

Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Problem Statement

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 bitwise xor of all the elements becomes zero. If no such non-negative integer exists, print -1.

Sample Test Cases

Input: 3
       5 3 1
Output: 1 
Explanation:
After adding 1 to all the elements, the array will become: A = { 2, 4, 6}.
Now xor of all the elements is 2^4^6 = 0.
Therefore, 1 can be the possible answer.

Input: 3
       3 4 6
Output: -1
Explanation: No such non-negative integer exist. 
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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!

Previous article
Generate All Binary Numbers in the Range [L, R]
Next article
Count of Subsets having Maximum Possible XOR Value
Live masterclass