Bitwise Operators: Given a number “n”, calculate xor of 1 to n

Problem Statement:

You are given an int value “n”, calculate the XOR from 1 to n.

Example:

Input : n = 6
Output : 7
1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 = 7

Solution 1: Naive approach

In this approach, we traverse all numbers from 1 to n.

Then do XOR of number one by one

Time Complexity: O(n)

Space Complexity: O(1)

Solution 2: Efficient Approach

Find the remainder of n by doing modulus it with 4.

If remainder = 0, then XOR will be same as n
If remainder = 1, then XOR will be same as 1
If remainder = 2, then XOR will be same as n+1
If remainder = 3, then XOR will be same as 0

Time Complexity: O(1)

Space Complexity: O(1)

Code Solution

#include<iostream>
using namespace std;

int soultion_1(int n)
{
    int result = 0;
    
    for (int i = 1; i <= n; i++) {
        result = result ^ i; 
    }
    return result;
}

int soultion_2(int n)
{
  
  if (n % 4 == 0)
    return n;

  if (n % 4 == 1)
    return 1;

  if (n % 4 == 2)
    return n + 1;

  return 0;
}

int main() {
  
    int x = 10, y = 15;

    cout << soultion_1(10)<<"\n";
    cout << soultion_2(10);
    return 0; 
}

Output

11
11