<<< Previous Next >>>
Basic Programming > Bit Manipulation > Basics of Bit Manipulation
Alice has integers and . Let be the number we get by xoring all numbers in the range (including and ). He recently learnt about even and odd numbers and wonders what will be the parity on .
Input Format:
First line contains integers and
Output Format:
Print "even" if the number is even else print "odd" without the quotes.
Constraints:
Here L is 3 and R is 5
Now X=(3^4^5) where '^' represents bitwise xor.
X=2.
Since X is even, the output is "even".
My Code after understanding the problem with ChatGPT
L, R = map(int, input().split())
count_odds_L = (L)//2 # L is included in the range, so we count odds till L-1
count_odds_R = (R+1)//2
count_odds_LR = count_odds_R - count_odds_L
if count_odds_LR % 2 == 0:
print("even")
else:
print("odd")
I am learning Data Structures and Algorithms. I will provide a screenshot of a problem statement. Your task is NOT to directly give me the final code solution unless I explicitly ask for it. Instead, please do the following: 1. First, carefully restate the problem in your own words to confirm correct understanding. - If anything is unclear in the screenshot, ask me clarification questions before proceeding. 2. Identify: - What category of problem this is (e.g., prefix sum, greedy, DP, two pointers, binary search, graph, etc.) - What core DSA concepts are being tested - What mathematical observations (if any) are involved - What constraints are important and how they affect the approach 3. Explain: - What naive/brute-force solution would look like - Why that may or may not work under the given constraints - What optimization insight is required 4. Clearly explain the key trick or insight needed to solve it. - Why does that trick work? - What pattern should I remember for future problems? 5. Provide: - The time complexity and space complexity of the optimal approach - Why it satisfies the constraints 6. If there are multiple valid approaches, compare them. 7. Only after all conceptual explanation, provide clean and correct Python code. 8. Avoid guessing unclear details. - If any part of the screenshot is ambiguous, ask me instead of assuming. Focus on correctness over speed. Be explicit in reasoning.
Let's go through this carefully step by step, exactly as you requested.
1. Restating the Problem (Understanding Check)
You are given two integers L and R.
Define:
where ⊕ represents the bitwise XOR operation.
Your task is not to compute X, but only determine:
-
If X is even → print
"even" -
If X is odd → print
"odd"
Important details
-
The range includes both L and R
-
Constraints:
Example from the prompt:
Input:
3 5
Compute:
X = 3 ^ 4 ^ 5
3 ^ 4 = 7
7 ^ 5 = 2
Since 2 is even → output "even"
2. Problem Category
This problem falls under:
Primary Category
-
Bit Manipulation
Secondary Concepts
-
XOR properties
-
Mathematical observation
-
Parity analysis
3. Core DSA Concepts Being Tested
1️⃣ XOR Properties
Important XOR identities:
a ^ a = 0
a ^ 0 = a
XOR is associative and commutative
Example:
1 ^ 2 ^ 3 ^ 4
= ((1 ^ 2) ^ 3) ^ 4
2️⃣ Parity of Numbers
A number is:
even → last bit = 0
odd → last bit = 1
Example:
6 = 110
7 = 111
3️⃣ XOR Parity Observation
The last bit of the XOR result equals:
XOR of the last bits of all numbers
So:
Parity(X) = XOR of parities of all numbers
This is the key observation.
4. Important Constraint Insight
The constraint is huge:
R ≤ 10^18
So we cannot iterate from L to R.
Even if the range is small sometimes, worst case could be:
10^18 operations
Which is completely impossible.
So we must solve it mathematically in O(1).
5. Brute Force Approach
Idea
Compute:
X = 0
for i in range(L, R+1):
X ^= i
Then check:
if X % 2 == 0:
print("even")
else:
print("odd")
Time Complexity
O(R − L)
Worst case:
10^18
This will not work.
6. Key Mathematical Insight
We do NOT need the entire XOR result.
We only need whether the result is even or odd.
A number is odd if its last bit = 1.
Critical XOR Observation
The last bit of XOR equals:
XOR of the last bits of all numbers
Now observe:
even number → last bit = 0
odd number → last bit = 1
So the final XOR parity becomes:
1 ^ 1 ^ 1 ^ ... (for each odd number)
Thus:
Parity(X) = XOR of all odd-number indicators
Which means:
If count_of_odds is even → result is even
If count_of_odds is odd → result is odd
So the entire problem reduces to:
Count how many odd numbers exist in [L, R]
7. Counting Odd Numbers in a Range
Number of odds ≤ N:
(N + 1) // 2
Example:
N = 5
1,2,3,4,5
odds = 3
(5+1)//2 = 3
Odds in [L, R]
odds = odds_up_to_R − odds_up_to_(L−1)
Which simplifies to:
odds = (R + 1)//2 − L//2
8. Determining the Result
if odds % 2 == 0:
result = even
else:
result = odd
9. Time and Space Complexity
Time Complexity
O(1)
Just a few arithmetic operations.
Space Complexity
O(1)
No extra storage.
This easily satisfies:
R ≤ 10^18
10. Pattern to Remember (Important)
Whenever a problem asks:
XOR parity
XOR odd/even
last bit of XOR
Remember:
XOR parity depends only on how many odd numbers exist.
Because:
Even numbers contribute 0
Odd numbers contribute 1
So the final parity becomes:
count_of_odds % 2
11. Python Implementation
PythonL, R = map(int, input().split())
# count odd numbers in [L, R]
odds = (R + 1) // 2 - L // 2
if odds % 2 == 0:
print("even")
else:
print("odd")
If you'd like, I can also show you another interesting XOR trick that solves this using the XOR prefix pattern (0..n) which appears frequently in competitive programming. It’s a pattern worth memorizing for interviews.
Sure show me XOR prefix pattern
Great. The XOR prefix pattern is one of the most useful tricks in bit manipulation problems. It appears very often in competitive programming and interviews.
Let's build the intuition step-by-step.
1. The Core Idea
Instead of computing
directly, we use a prefix XOR function:
Then the XOR of a range becomes:
This works because XOR cancels duplicates.
Example:
f(5) = 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 5
f(2) = 0 ^ 1 ^ 2
Now:
f(5) ^ f(2)
= (0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 5) ^ (0 ^ 1 ^ 2)
Everything before 3 cancels:
= 3 ^ 4 ^ 5
Which is exactly the range we wanted.
2. The Magical Pattern of f(n)
Now let's compute small values.
| n | XOR(0..n) |
|---|---|
| 0 | 0 |
| 1 | 1 |
| 2 | 3 |
| 3 | 0 |
| 4 | 4 |
| 5 | 1 |
| 6 | 7 |
| 7 | 0 |
| 8 | 8 |
Look at the pattern.
n % 4 == 0 → result = n
n % 4 == 1 → result = 1
n % 4 == 2 → result = n + 1
n % 4 == 3 → result = 0
This repeats every 4 numbers.
3. Why Does This Pattern Exist?
Because XOR behaves cyclically in binary.
Example:
0 ^ 1 ^ 2 ^ 3 = 0
Binary:
0 = 000
1 = 001
2 = 010
3 = 011
All bits cancel out.
Then the pattern restarts.
So the XOR prefix repeats every 4 numbers.
4. Computing XOR of Any Range
Now we can compute:
using:
xor(L..R) = f(R) ^ f(L-1)
where f(n) follows the 4-pattern rule.
5. Example
Compute:
3 ^ 4 ^ 5
Step 1
f(5)
5 % 4 = 1
→ f(5) = 1
Step 2
f(2)
2 % 4 = 2
→ f(2) = 3
Step 3
1 ^ 3 = 2
Correct result.
6. How This Helps Our Problem
We want to know:
Is X even or odd?
Compute:
X = f(R) ^ f(L-1)
Then check:
X % 2
Since f(n) is O(1) to compute, the whole solution is O(1).
Works even for:
R = 10^18
7. Python Implementation Using XOR Prefix
Pythondef prefix_xor(n):
if n % 4 == 0:
return n
elif n % 4 == 1:
return 1
elif n % 4 == 2:
return n + 1
else:
return 0
L, R = map(int, input().split())
X = prefix_xor(R) ^ prefix_xor(L - 1)
if X % 2 == 0:
print("even")
else:
print("odd")
8. Important Pattern to Memorize
You should memorize this table:
XOR(0..n)
n % 4 = 0 → n
n % 4 = 1 → 1
n % 4 = 2 → n+1
n % 4 = 3 → 0
This appears in problems like:
-
XOR of a range
-
Missing number problems
-
XOR puzzles
-
Bit manipulation interviews
9. Interview Insight
Interviewers often test whether you know this trick.
A typical question:
Find XOR of numbers from 1 to 10^12
Brute force is impossible.
But with this trick:
O(1)
If you'd like, I can also show you a very common FAANG interview problem that uses this same XOR pattern:
"Find the missing number in an array using XOR"
It’s one of the cleanest XOR tricks you’ll ever see.
sure, proceed
Great 👍 — this is one of the cleanest XOR applications in DSA and appears frequently in interviews.
Let's go step-by-step.
1. The Classic Problem
You are given an array containing n distinct numbers taken from:
Exactly one number is missing.
Your task:
Find the missing number.
Example
Input:
nums = [3,0,1]
Numbers should be:
0,1,2,3
But 2 is missing.
Output:
2
2. Key Constraint Insight
The array length is:
n
But the expected numbers are:
0 → n
So there are:
n + 1 numbers
Meaning one is missing.
3. Brute Force Idea
Approach
For each number from 0..n:
check if it exists in the array
Complexity
Time = O(n²)
Too slow.
4. Better Approach (Hash Set)
Store all numbers in a set.
Then check:
for i in range(n+1):
if i not in set:
return i
Complexity
Time = O(n)
Space = O(n)
Good, but not optimal.
5. Mathematical Approach
Expected sum:
Subtract actual sum.
Example:
n = 3
expected = 6
actual = 4
missing = 2
Complexity
Time = O(n)
Space = O(1)
This works, but can overflow in some languages.
6. XOR Approach (Elegant Trick)
This is where XOR shines.
Key property:
a ^ a = 0
a ^ 0 = a
Example:
3 ^ 3 = 0
Numbers cancel each other.
7. XOR Idea
Compute XOR of:
all numbers from 0..n
and
all numbers in the array
Everything cancels except the missing number.
Example
nums = [3,0,1]
Expected numbers:
0 1 2 3
Compute:
(0 ^ 1 ^ 2 ^ 3) ^ (3 ^ 0 ^ 1)
Rearrange:
0 ^ 0 ^ 1 ^ 1 ^ 3 ^ 3 ^ 2
Everything cancels:
= 2
8. Visualization
Expected XOR: 0 ^ 1 ^ 2 ^ 3
Array XOR: 3 ^ 0 ^ 1
--------------------------------
Result: 2
9. Why This Works
Because XOR behaves like perfect cancellation.
Every number appearing twice disappears.
Only the missing number remains.
10. Complexity
Time
O(n)
Space
O(1)
No extra memory needed.
11. Python Implementation
Pythondef missingNumber(nums):
n = len(nums)
xor_all = 0
xor_array = 0
for i in range(n + 1):
xor_all ^= i
for num in nums:
xor_array ^= num
return xor_all ^ xor_array
12. Even Cleaner Version
We can combine both loops.
Pythondef missingNumber(nums):
n = len(nums)
xor = n
for i in range(n):
xor ^= i ^ nums[i]
return xor
13. Pattern to Remember
Whenever you see:
-
missing number
-
unique number
-
numbers appearing twice except one
Think immediately:
XOR
Common problems:
1️⃣ Missing number
2️⃣ Single number (LeetCode classic)
3️⃣ Two unique numbers
4️⃣ XOR range problems
5️⃣ Bit puzzles
14. A Very Important Interview Variant
Another famous problem:
Every element appears twice except one.
Find the unique number.
Example:
[4,1,2,1,2]
Answer:
4
Solution:
XOR all numbers
Everything cancels except the unique one.
If you'd like, I can also show you one of the most powerful XOR interview tricks:
Finding two unique numbers when all others appear twice — this is a classic Google / Meta interview problem and introduces a very clever bit-partition trick.
