Help Alice to find the Parity (Medium)

Index of "Algorithms: Design and Analysis"
<<< Previous    Next >>>

Basic Programming > Bit Manipulation > Basics of Bit Manipulation

Problem

Alice has $2$ integers $L$ and $R$. Let $X$ be the number we get by xoring all numbers in the range $[L,R]$ (including $L$ and $R$). He recently learnt about even and odd numbers and wonders what will be the parity on $X$.

Input Format:

First line contains $2$ integers $L$ and $R$ 

Output Format:

Print "even" if the number $X$ is even else print "odd" without the quotes. 

Constraints:

$1 \leq L \leq R \leq 10^{18}$

Sample Input

3 5

Sample Output

even

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

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".

 

 

Contributers:

Prakhar Jalan

Geetartha Kaustav

Solve on HackerEarth

---

---

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:

$$X = L \oplus (L+1) \oplus (L+2) \oplus ... \oplus R$$

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:

$$1 \le L \le R \le 10^{18}$$

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

Python
L, 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

$$L \oplus (L+1) \oplus ... \oplus R$$

directly, we use a prefix XOR function:

$$f(n) = 0 \oplus 1 \oplus 2 \oplus ... \oplus n$$

Then the XOR of a range becomes:

$$L \oplus (L+1) \oplus ... \oplus R = f(R) \oplus f(L-1)$$

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:

$$L \oplus ... \oplus R$$

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

Python
def 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:

$$0,1,2,3,...,n$$

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:

$$\frac{n(n+1)}{2}$$

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

Python
def 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.

Python
def 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.