Single Number (XOR Self-Cancellation)

▶

Steps

setup

Initialize result to 0

We start by setting the result variable to 0, which will hold the XOR of all numbers.

💡 Starting with 0 is important because XOR with 0 leaves the other number unchanged, so result accumulates the XOR progressively.

Line:

result = 0

💡 Result initialized to zero means the first XOR will just set result to the first number.

traverse

XOR result with first number 2

We take the first number 2 and XOR it with the current result (0).

💡 XOR with 0 sets result to the first number, starting the accumulation.

Line:

result ^= num  # num = 2

💡 XOR with zero copies the number into result.

compare

Visual confirmation of cancellation

Observe how the bits of the two 2's cancel each other out in the XOR operation.

💡 This cancellation is the core property that makes XOR useful for this problem.

Line:

result ^= num  # num = 2 (second occurrence)

💡 Identical bits XOR to zero, removing duplicates.

traverse

XOR result with second number 2

Next, XOR the current result (2) with the second number (2).

💡 XORing a number with itself cancels out to zero.

Line:

result ^= num  # num = 2

💡 XOR of identical numbers is zero, so result will reset to 0.

compare

Bitwise XOR operation detail

Focus on the least significant bit (LSB) where the XOR operation flips bits.

💡 XOR flips bits where bits differ, which is how unique bits survive.

Line:

result ^= num

💡 Bit flipping at differing bits isolates unique bits.

traverse

XOR result with third number 1

Finally, XOR the current result (0) with the last number (1).

💡 XOR with zero sets result to the last number, which is the unique number.

Line:

result ^= num  # num = 1

💡 Result now holds the unique number after all cancellations.

traverse

End of iteration

All numbers have been processed; result holds the single number.

💡 No more numbers to XOR; the final result is the unique number.

Line:

return result

💡 The XOR self-cancellation property guarantees the unique number remains.

reconstruct

Result after processing all numbers

The final result variable now holds the unique number 1 after all XOR operations.

💡 The algorithm leverages XOR's properties to isolate the unique number efficiently.

Line:

return result

💡 The final XOR result is the single number that appears once.

reconstruct

Return the unique number

The algorithm returns the final result, which is the single number 1.

💡 Returning the result completes the algorithm.

Line:

return result

💡 The output matches the expected unique number.

prune

Summary: XOR self-cancellation property

This step summarizes how XOR cancels duplicates and isolates the unique number.

💡 Understanding this property is the key to solving similar problems efficiently.

💡 XOR of a number with itself is zero; XOR with zero is the number; XOR is commutative and associative.

def singleNumber(nums):
    result = 0;  # STEP 1: Initialize result
    for num in nums:
        result ^= num;  # STEP 2-6: XOR with each number
    return result;  # STEP 7-9: Return final unique number

if __name__ == '__main__':
    print(singleNumber([2, 2, 1]))  # Output: 1

📊

Single Number (XOR Self-Cancellation) - Watch the Algorithm Execute, Step by Step

Watching each XOR operation visually reveals how pairs of identical numbers eliminate each other's bits, making the unique number stand out.

Initialize result

A

0

0

0

0

0

0

0

0

=0

B

result ^= 2

A

0

1

0

=0

B

0

1

0

=2

──────

=

0

1

0

=2

💡 XOR with zero copies bits of 2 into result.

2 XOR 2 = 0

A

0

1

0

=2

B

0

1

0

=2

────────────────

=

0

0

0

0

0

0

0

0

=0

💡 Bits cancel out when identical.

result ^= 2

A

0

1

0

=2

B

0

1

0

=2

────────────────

=

0

0

0

0

0

0

0

0

=0

💡 XOR of identical bits cancels to zero.

XOR at LSB

A

0

0

0

0

0

0

0

0

=0

B

0

1

=1

────

=

0

1

=1

💡 LSB flips from 0 to 1 because bits differ.

result ^= 1

A

0

0

0

0

0

0

0

0

=0

B

0

1

=1

────

=

0

1

=1

💡 XOR with zero copies bits of 1 into result.

Final result

A

0

1

=1

B

────

=

0

1

=1

💡 Final result is the unique number.

Final result

A

0

1

=1

B

────

=

0

1

=1

💡 Unique number isolated in result.

Return result

A

0

1

=1

B

────

=

0

1

=1

💡 Final answer returned.

XOR properties summary

A

0

1

=1

B

💡 XOR cancels duplicates, isolates unique.

Key Takeaways

✓ XOR of a number with itself is zero, which cancels duplicates.

This property is not obvious from code alone but is fundamental to the algorithm's correctness.

✓ XOR with zero leaves the number unchanged, allowing accumulation.

Starting with zero means the first XOR sets the result cleanly.

✓ The XOR operation is commutative and associative, so order doesn't matter.

This means the algorithm works regardless of input order, which is a powerful insight.

Practice

1. You need to determine if a given positive integer can be expressed as 4 raised to some integer power (i.e., n = 4^k for k ≥ 0). Which approach guarantees an optimal O(1) time solution without loops or recursion?

easy

A. Use logarithms to check if log base 4 of the number is an integer.

B. Iteratively divide the number by 4 until it becomes 1 or a non-divisible remainder is found.

C. Check if the number is a power of two and then verify if the set bit is in an even position using bitmasking.

D. Use dynamic programming to build up powers of four and compare with the number.

Solution

1. Step 1: Understand the problem requirement

   The problem asks for a constant-time check to determine if a number is a power of four, which means no loops or recursion.

2. Step 2: Evaluate approaches for O(1) time

   Using bitmasking to check if the number is a power of two and if the single set bit is in an even position is a known O(1) approach. Logarithm checks involve floating point operations and can have precision issues, so they are not guaranteed to be optimal or reliable in constant time. Iterative division and dynamic programming are not O(1).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Bitmasking approach uses constant time bit operations [OK]

Hint: Bitmasking checks power of two and bit position in O(1)

Common Mistakes:

• Confusing power of two check with power of four
• Using loops despite O(1) requirement
• Relying on floating point logarithm checks which can be imprecise

2. Given the following Python code that generates all subsets of nums = [1, 2, 3], what is the value of res after the function completes?

easy

A. [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

B. [[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]

C. [[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]

D. [[], [1], [1, 3], [1, 2], [1, 2, 3], [2], [2, 3], [3]]

Solution

1. Step 1: Trace backtrack calls and subsets added

   Initially, empty subset [] is added. Then 1 is added, subsets with 1 are generated, then 2, then 3, backtracking after each.

2. Step 2: Confirm order and completeness of subsets

   Subsets are generated in lexicographic order due to sorting and incremental indices: [], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3].

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Matches expected subsets order from backtracking [OK]

Hint: Backtracking adds subsets in sorted order [OK]

Common Mistakes:

• Confusing order of subsets or missing subsets

3. What is the time complexity of the Brian Kernighan's bit counting trick approach when counting set bits for all numbers from 0 to n?

medium

A. O(n * k) where k is the average number of set bits per number

B. O(n) because each number is processed in constant time

C. O(n * log n) because each number requires checking all bits

D. O(n^2) due to nested loops over bits and numbers

Solution

1. Step 1: Identify loops and operations

   Outer loop runs n+1 times; inner loop runs as many times as set bits in each number.

2. Step 2: Analyze average inner loop iterations

   Each iteration clears one set bit, so total inner loop iterations over all numbers is proportional to total set bits, roughly n * k.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Counting bits per number depends on number of set bits, not all bits [OK]

Hint: Time depends on total set bits, not total bits [OK]

Common Mistakes:

• Assuming O(n log n) because of bit length
• Thinking each number is constant time
• Confusing nested loops as quadratic

4. Suppose you need to reverse bits of a 64-bit unsigned integer instead of 32-bit. Which modification to the optimal divide and conquer mask approach is correct?

hard

A. Extend masks to 64-bit constants and add an additional step shifting by 32 bits with proper masking.

B. Apply the 32-bit mask approach directly without changes; it works for any bit width.

C. Use the brute force bit-by-bit reversal loop since masks only work for 32 bits.

D. Use the same 32-bit masks and steps, but apply them twice to the lower and upper 32 bits separately.

Solution

1. Step 1: Understand mask size dependency

   The masks and shifts are designed for 32-bit integers and must be extended for 64-bit integers.

2. Step 2: Modify masks and add step

   Use 64-bit masks and add a final step shifting by 32 bits with masking to handle full 64-bit reversal.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   64-bit reversal requires 64-bit masks and an extra step [OK]

Hint: 64-bit reversal needs 64-bit masks and extra shift step [OK]

Common Mistakes:

• Trying to reuse 32-bit masks directly
• Splitting 64-bit into two 32-bit halves without merging
• Assuming brute force is only option for 64-bit

5. Suppose the UTF-8 validation problem is extended to allow the input data array to be a stream where bytes arrive incrementally, and you must validate the stream in real-time without storing the entire input. Which modification to the optimal algorithm is necessary to correctly validate the stream?

hard

A. Maintain a continuation byte counter and validate each byte as it arrives, returning False immediately on invalid bytes.

B. Use recursion to validate each character once the full character bytes are available.

C. Buffer all bytes until a full character is received before validating to handle partial characters.

D. Reset the continuation byte counter to zero after every 4 bytes to avoid overflow.

Solution

1. Step 1: Understand streaming constraints

   In a stream, bytes arrive incrementally and must be validated on the fly without full buffering.

2. Step 2: Adapt the continuation byte counter approach

   Maintain the continuation byte counter state across bytes and validate each byte immediately, returning False if invalid.

3. Step 3: Avoid buffering or recursion

   Buffering or recursion delays validation and is not suitable for real-time streaming.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Continuation counter with immediate validation fits streaming constraints [OK]

Hint: Maintain state and validate bytes immediately in streaming [OK]

Common Mistakes:

• Buffering entire characters breaks streaming
• Resetting counter incorrectly loses state