XOR and Lucky Number

Intuition

The intuition will be very straightforward; for every query, we will find the XOR value of all the numbers between each pair of indices possible. After finding out the XOR value, we can check if it's equal to 'K' or not. If so, we will increase the 'COUNT' variable, which contains our final answer for that particular query. Things will become more clear from the following code.

Code

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

int count(vector<int> arr, int l, int r, int k)
{
    int count = 0;
    l--;
    r--;

    /*Looping through all possible cases */
    for (int i = l; i <= r; i++)
    {
        int XOR = 0;
        for (int j = i; j <= r; j++)
        { /*Calculating the value of XOR */
            XOR = XOR ^ arr[j];

            /*Checking if it equals to 'K' */
            if (XOR == k)
                count++;
        }
    }
    return count;
}
int main()
{

    int n, m, k;
    cin >> n >> m >> k;
    vector<int> arr(n);

    /*Input array */
    for (int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        arr[i] = x;
    }

    /*Taking queries as input */
    for (int i = 0; i < m; i++)
    {
        int l, r;
        cin >> l >> r;
        cout << count(arr, l, r, k) << endl;
    }
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Input

5 3 1
1 1 1 1 1
1 5
2 4
1 3

You can also try this code with Online C++ Compiler

Run Code

Output

9
4
4

You can also try this code with Online C++ Compiler

Run Code

Complexities

Time Complexity

O(M * N * N) ,

Reason: As we are looping over 'M queries, it will cost us O(M) time, and inside each query, we are using a nested loop which in the worst case will cost O(N * N) time. Thus, the overall time complexity to O(M) * O(N * N) ~ O(M * N * N).

Space Complexity

O(1).

Reason: We are not using any extra variable space. 

Check out this problem - XOR Queries On Tree

FAQs

1. What is the XOR of two numbers?
   The logical XOR takes two boolean operands and returns true if and only if they are not the same. As a result, it returns false if the two operands have the same value.
    
2. What are the different bitwise operators?
   There are 6 types of bitwise operators. These are AND(&), OR(|), NOT(~), XOR(^), Left Shift(<<), Right Shift(>>).
    
3. How to swap two numbers using XOR?
   Let the two numbers that are given to us be a and b. Now we will follow the following steps:
   a=a XOR b
   b=a XOR b ( As a XOR b XOR b = a)
   a=a XOR b (As a XOR b XOR a = b) 
    
4. What is the XOR of the same numbers?
   We know that if we take XOR of 1 with 1 answer is equal to 0 and if we take XOR of 0 with 0, the answer is still equal to zero; thus, we can infer that XOR of the same numbers will be equal to 0.
    
5. To what number should I take XOR of any given number ‘N’, so that the result is ‘N’? 
   We know that in the XOR operation, It returns true if and only if they are not of the same value; thus, to get the same number again, we should take XOR of ‘N’ with 0.

Key Takeaways

We saw how we solved the problem 'XOR and Lucky Number' using the bitwise operator XOR. Some other problems that involve bitwise operators are Minimum XOR, Find a Number X Such that XOR of Given Array after Adding X to Each Element is 0, etc. Now don't waste any more time and head over to our practice platform Coding Ninjas Studio to practice top problems on every topic, interview experiences, and many more.
Till then, Happy Coding!