XOR From 1 to N Bit Pattern DSA Solution

Learning Outcome

After this lesson, you should be able to recognize the repeating pattern in cumulative XOR from 1 to n.

Problem Statement

Given n, return the XOR of all integers from 1 to n.

Input	Output	Why
`n = 10`	`11`	The cumulative XOR pattern repeats every 4 values, and 10 mod 4 equals 2, so the answer is n + 1.

Brute Force Approach

Loop from 1 to n and XOR every value. This works but costs O(n).

Optimized Approach

Use the known cycle: n mod 4 equals 0 -> n, 1 -> 1, 2 -> n + 1, and 3 -> 0.

Exact Pseudocode

remainder = n % 4
if remainder == 0:
  return n
if remainder == 1:
  return 1
if remainder == 2:
  return n + 1
return 0

Reference Code

class Solution:
    def xorTillN(self, n):
        remainder = n % 4
        if remainder == 0:
            return n
        if remainder == 1:
            return 1
        if remainder == 2:
            return n + 1
        return 0

Sample Dry Run

Step	State	Result
Observe cycle	xor(1)=1, xor(2)=3, xor(3)=0, xor(4)=4	Pattern repeats every 4
n = 10	10 mod 4 = 2	Use n + 1 case
Return	10 + 1	answer = 11

Complexity

Measure	Value	Reason
Time	O(1)	The answer comes from one modulo operation and constant checks.
Space	O(1)	No extra storage is used.

Edge Cases

If n = 0 and the range is empty, return 0.
The case n mod 4 = 2 returns n + 1.
Do not confuse cumulative XOR with sum.

Interview Checklist

Memorize or derive the four-case cycle.
Use n % 4 to choose the answer.
Handle n = 0 if the prompt allows it.

FAQs

Why does the cycle repeat every 4?

XORing consecutive integers produces a stable four-case pattern based on the low two bits.

Can this answer range XOR queries?

Yes. XOR from L to R can be built from xor(1..R) xor xor(1..L-1).

What is the core pattern?

Modulo-4 XOR cycle.

XOR From 1 to N: Modulo Cycle Pattern