XOR Operation in an Array Leetcode Solution  

Difficulty Level Easy
Frequently asked in Walmart Labs
algorithms Array Bit Manipulation Bits Bitwise-XOR coding Interview interviewprep LeetCode LeetCodeSolutions

Problem Statement  

In this problem we have to do XOR Operation in an Array of size n in which each element is equal to (start + 2*i) where i is the index of the element (0-indexed) and value of start is given.
We have to return the bitwise XOR of all elements of the array.

Example

n = 4, start = 3
8

Explanation:

Array nums is equal to [3, 5, 7, 9] where (3 ^ 5 ^ 7 ^ 9) = 8.
Where “^” corresponds to bitwise XOR operator.

n = 1, start = 7
7

Explanation:

Please click Like if you loved this article?

Array nums is equal to [7] , Hence xor  = 7.

Approach (Brute Force)  

We can simply run a for loop n times for i=0 to i=n-1. In for loop we will be doing bitwise xor of (start+2*i) with the current xor which we will store in a variable res.

Algorithm

1. create a variable ind to represent index of the element of the array and initialize with 0.
2. create a variable res to store the current xor during for loop and initialize with 0.
3. Run a for loop from ind=0 to ind=n-1.
4. Do bitwise xor of res with (start+ 2*i) i.e. element at index ind and store the result in res.
5. Return the res.

See also
Palindrome Linked List Leetcode Solution

Implementation for XOR Operation in an Array Leetcode Solution

C++ Program

#include <bits/stdc++.h>
using namespace std;

int xorOperation(int n, int start) {

    int ind=0;
    int res=0;
    for(ind=0;ind<n;ind++) res=res^(start+2*ind);

    return res;

}
int main() 
{
        int n=4;
        int start=3;
    cout<<xorOperation(n,start)<<endl;

  return 0; 
}
8

Java Program

import java.lang.*;

class XorOperation
{  
    public static int xorOperation(int n, int start) 
    {

        int ind=0;
        int res=0;
        for(ind=0;ind<n;ind++) res=res^(start+2*ind);

        return res;      
    }
    
    
    public static void main(String args[])
    {
        int n=4;
        int start=3;

        System.out.println(xorOperation(n,start));
        
    }
}
8

Complexity Analysis for XOR Operation in an Array Leetcode Solution

Time Complexity

O(N):  Where N is the given size of the array. As we are traversing the array in a single for loop for N elements. Hence time complexity is O(N).

Space Complexity 

O(1):  As we are not using any extra memory other than some variables. Hence extra space utilized is constant.

Approach (Bit Manipulation 

In the above problem we can see that difference between each next element is 2. That means either all the elements will be even or all will be odd. That makes a kind of a range but not consecutive i.e. it is having alternate values.

Using bit manipulation we can find bitwise xor of a range having consecutive elements in it in constant time. Let us see how, and then we will try to convert above problem into the problem below:

Lets suppose a range =[3,4,5,6,7,8,9,10] , and we have to apply xor in the range between first and last element.

Let x be any even number and y be the number next to x. i.e. y=x+1. We can easily analyze that xor of x and y will always be 1. Or xor of every even number and odd number next to it is always 1. Hence we can conclude that every even-odd  pairs between first and last number gives xor equal to 1.
i.e.   4^5=1,  6^7=1,  8^9=1

See also
Range Minimum Query (Square Root Decomposition and Sparse Table)

Now if the number of those pairs are odd then xor of the elements between 1st even number and last odd number will be 1, or else 0.
i.e.  4^5^6^7^8^9  =  1^1^1   = 1

Now we are only left with the numbers at the end positions which is 3 and 10. Hence our answer will be  3^1^10 = 8  as shown in figure below:

XOR Operation in an Array Leetcode Solution

Converting the problem into consecutive range XOR

In the above problem we can reduce the distance between each element from 2 to 1 if we right shift bitwise each element by 1 ( same as dividing by 2 ).  By doing this we are only affecting the last bit of the elements. So we first store the last bit of our ans by following cases :

1. If all the elements in array is odd and total number of elements is also odd, then  lastbit=1.
2. Else lastbit=0.

Now after we right shift each element by 1, our range becomes :

Please click Like if you loved this article?

start/2,  start/2  +1 , start/2  +2 ,  . . . .  ,  start/2  +(n-1) .

Where first= start/2   and last= start/2  + (n-1).

Now we can easily find out the xor of this range by finding bitwise xor of end elements and all even-odd pairs between them in constant time.

After finding xor we have to bitwise left shift the result by 1 to gain the original position of bits in our final answer. Finally add the lastbit to the result and return it.

Implementation for XOR Operation in an Array Leetcode Solution

C++ Program

#include <bits/stdc++.h>
using namespace std;

int xorOperation(int n, int start) {

    int lastbit;
    if(n%2==1  &&  start%2==1) lastbit=1;
    else lastbit=0;

    //after 1 right shift
    int first= start/2;
    int last= start/2+ n-1;

    int res=0;

    if(first%2==1)
    { 
        res^=first; 
        first++;
    }

    if(last%2==0)
    {
        res^=last;
        last--;
    }


    int pairs=0;            //in between pairs
    if(first<last)   pairs= (last-first+1)/2;    
    if(pairs%2==1) res^=1;   

    res<<=1;                // back to 1 left shift
    res+=lastbit;           // attaching last bit

    return res;

}
int main() 
{
        int n=4;
        int start=3;
    cout<<xorOperation(n,start)<<endl;

  return 0; 
}
8

Java Program

import java.lang.*;

class Rextester
{  
    public static int xorOperation(int n, int start) 
    {

        int lastbit;
        if(n%2==1  &&  start%2==1) lastbit=1;
        else lastbit=0;

        //after 1 right shift
        int first= start/2;
        int last= start/2+ n-1;

        int res=0;

        if(first%2==1)
        { 
            res^=first; 
            first++;
        }

        if(last%2==0)
        {
            res^=last;
            last--;
        }


        int pairs=0;            //in between pairs
        if(first<last)   pairs= (last-first+1)/2;    
        if(pairs%2==1) res^=1;   

        res<<=1;                // back to 1 left shift
        res+=lastbit;           // attaching last bit

        return res;     
    }
    
    
    public static void main(String args[])
    {
        int n=4;
        int start=3;

        System.out.println(xorOperation(n,start));
        
    }
}
8

Complexity Analysis for XOR Operation in an Array Leetcode Solution

Time Complexity

O(1):  As we are not traversing over all the elements of the array, using bit manipulation we have done it in constant time.

See also
Range sum queries without updates

Space Complexity 

O(1):  Here also extra memory used is constant.

Please click Like if you loved this article?