Calculate XOR from 1 to n

Problem Statement

Given an integer n, calculate the XOR of all numbers from 1 to n, i.e., compute:

1 ^ 2 ^ 3 ^ 4 ^ ... ^ n

Constraints:

1 ≤ n ≤ 10^9

Examples

Example 1:

Input: n = 5
Output: 1

Explanation: 1 ^ 2 ^ 3 ^ 4 ^ 5 = 1

Example 2:

Input: n = 7
Output: 0

Explanation: 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 = 0

Different Approaches

1️⃣ Brute Force (Iterative XOR)

Intuition:

Just iterate from 1 to n and compute the XOR one by one.

Approach:

1. Initialize res = 0
2. From i from 1 to n, do res = res ^ i
3. Return res

Code:

#include <iostream>
using namespace std;

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

int main() {
    int n = 5;
    cout << "XOR from 1 to " << n << " is: " << xorBruteForce(n) << endl;
    return 0;
}

Complexity Analysis:

• Time Complexity:O(n)
• Space Complexity:O(1)

2️⃣ Bit Manipulation

Intuition:

There is a pattern in XOR from 1 to n.

Let's look at small values of n:

We can see this pattern:

n % 4 == 0 → result = n
n % 4 == 1 → result = 1
n % 4 == 2 → result = n + 1
n % 4 == 3 → result = 0

This pattern holds due to the properties of XOR:

• XOR is associative and commutative.
• XOR from 1 to n has a repeating cycle of 4.

Code:

#include <iostream>
using namespace std;

int xorFrom1ToN(int n) {
    if (n % 4 == 0)
        return n;
    else if (n % 4 == 1)
        return 1;
    else if (n % 4 == 2)
        return n + 1;
    else
        return 0;
}

int main() {
    int n;
    cout << "Enter n: ";
    cin >> n;

    cout << "XOR from 1 to " << n << " is: " << xorFrom1ToN(n) << endl;
    return 0;
}

Complexity Analysis:

• Time Complexity:O(1)
  • Just a modulo operation and constant-time conditionals
• Space Complexity:O(1)
  • Only a few variables used