Two Non Repeating Elements in Array Using XOR in DSA Python - Build from Scratch

Two Non Repeating Elements in Array Using XOR

📖 Scenario: Imagine you have a list of numbers where every number appears twice except for two unique numbers that appear only once. You want to find those two unique numbers quickly without using extra space.

🎯 Goal: Build a Python program that finds the two non-repeating elements in an array using the XOR operation.

📋 What You'll Learn

Create a list called numbers with the exact values: [2, 3, 7, 9, 2, 3, 9, 11]

Create a variable called xor_all and initialize it to 0

Use a for loop with variable num to XOR all elements in numbers and store the result in xor_all

Find the rightmost set bit of xor_all and store it in a variable called rightmost_set_bit

Create two variables num1 and num2 initialized to 0

Use a for loop with variable num to divide numbers into two groups based on rightmost_set_bit and XOR separately to find the two unique numbers

Print the two unique numbers num1 and num2 separated by a space

💡 Why This Matters

🌍 Real World

Finding unique items in large datasets quickly without extra memory is useful in error detection, network packet analysis, and data cleaning.

💼 Career

Bitwise operations and efficient algorithms are important skills for software engineers, especially in systems programming, embedded systems, and performance-critical applications.

1

Create the list of numbers

Create a list called numbers with these exact values: [2, 3, 7, 9, 2, 3, 9, 11]

DSA Python

# Create the list called numbers with the given values
# Your code here

Hint

Use square brackets to create a list and separate numbers with commas.

2

Initialize XOR accumulator

Create a variable called xor_all and set it to 0

DSA Python

numbers = [2, 3, 7, 9, 2, 3, 9, 11]
# Create a variable called xor_all and set it to 0
# Your code here

Hint

Use = to assign 0 to xor_all.

3

XOR all elements in the list

Use a for loop with variable num to XOR all elements in numbers and store the result in xor_all

DSA Python

numbers = [2, 3, 7, 9, 2, 3, 9, 11]
xor_all = 0
# Use a for loop with variable num to XOR all elements in numbers
# Your code here

Hint

Use for num in numbers: and inside the loop update xor_all ^= num.

4

Find and print the two unique numbers

Find the rightmost set bit of xor_all and store it in rightmost_set_bit. Then create two variables num1 and num2 initialized to 0. Use a for loop with variable num to divide numbers into two groups based on rightmost_set_bit and XOR separately to find the two unique numbers. Finally, print num1 and num2 separated by a space.

DSA Python

numbers = [2, 3, 7, 9, 2, 3, 9, 11]
xor_all = 0
for num in numbers:
    xor_all ^= num
# Find rightmost set bit and store in rightmost_set_bit
# Create num1 and num2 initialized to 0
# Use a for loop with num to separate and XOR numbers
# Print num1 and num2 separated by space
# Your code here

Hint

The rightmost set bit can be found using xor_all & (-xor_all). Use two variables to XOR numbers based on this bit. Finally, print the two unique numbers.

Practice

1. What is the main purpose of using XOR operation to find two non-repeating elements in an array where every other element repeats twice?

easy

A. To sort the array in ascending order

B. To count the frequency of each element

C. To cancel out all repeating elements and isolate the XOR of the two unique elements

D. To reverse the array elements

Solution

1. Step 1: Understand XOR properties

   XOR of a number with itself is 0, and XOR with 0 is the number itself. This helps cancel out repeating elements.

2. Step 2: Apply XOR on all elements

   When XOR is applied on the entire array, all repeating elements cancel out, leaving XOR of the two unique elements.

3. Final Answer:

   To cancel out all repeating elements and isolate the XOR of the two unique elements -> Option C

4. Quick Check:

   XOR cancels duplicates = isolate unique elements [OK]

Hint: XOR duplicates become zero, leaving unique elements XOR [OK]

Common Mistakes:

• Thinking XOR sorts the array
• Using XOR to count frequencies
• Assuming XOR reverses elements

2. Which of the following Python code snippets correctly initializes the XOR of all elements in a list named arr to zero before processing?

easy

A. xor = 1

B. xor = 0

C. xor = arr[0]

D. xor = None

Solution

1. Step 1: Initialize XOR variable

   We start XOR with 0 because XOR with 0 returns the other number unchanged.

2. Step 2: Confirm initialization correctness

   Starting with 0 ensures the first XOR operation correctly sets the value to the first element.

3. Final Answer:

   xor = 0 -> Option B

4. Quick Check:

   Initialize XOR with 0 for correct accumulation [OK]

Hint: Start XOR with 0 to accumulate correctly [OK]

Common Mistakes:

• Initializing XOR with 1 causes wrong results
• Using first element without XOR 0 initialization
• Setting XOR to None causes errors

3. What will be the output of the following Python code?

arr = [2, 3, 7, 9, 2, 3]
xor = 0
for num in arr:
    xor ^= num
print(xor)

medium

A. 0

B. 9

C. 7

D. 14

Solution

1. Step 1: XOR all elements in the array

   Calculate XOR stepwise: 0^2=2, 2^3=1, 1^7=6, 6^9=15, 15^2=13, 13^3=14.

2. Step 2: Final XOR value

   The final XOR after processing all elements is 14.

3. Final Answer:

   14 -> Option D

4. Quick Check:

   Stepwise XOR = 14 [OK]

Hint: XOR all elements stepwise to find combined XOR [OK]

Common Mistakes:

• Forgetting XOR is cumulative and order matters
• Mistaking XOR with addition
• Stopping XOR early

4. Identify the error in the following code snippet that attempts to find two non-repeating elements using XOR:

arr = [4, 1, 2, 1, 2, 5]
xor = 0
for num in arr:
    xor ^= num
set_bit = xor & ~(xor - 1)
num1 = 0
num2 = 0
for num in arr:
    if (num & set_bit) > 0:
        num1 ^= num
    else:
        num2 ^= num
print(num1, num2)

medium

A. No error, code works correctly

B. XOR initialization should be arr[0] instead of 0

C. Incorrect calculation of set_bit using bitwise NOT

D. Using > 0 instead of != 0 in if condition

Solution

1. Step 1: Check set_bit calculation

   set_bit = xor & ~(xor - 1) correctly isolates rightmost set bit.

2. Step 2: Verify partition and XOR groups

   Elements are split by set_bit and XORed separately to find unique elements.

3. Step 3: Confirm output correctness

   Code correctly prints the two unique numbers without errors.

4. Final Answer:

   No error, code works correctly -> Option A

5. Quick Check:

   Correct set_bit and partitioning = code works [OK]

Hint: Use xor & ~(xor-1) to find rightmost set bit correctly [OK]

Common Mistakes:

• Misusing bitwise NOT causing wrong set_bit
• Initializing XOR incorrectly
• Using wrong condition in if statement

5. Given an array arr = [10, 20, 10, 30, 40, 20], which of the following Python code snippets correctly finds the two non-repeating elements using XOR and prints them in ascending order?

hard

A. xor = 0
for num in arr:
xor ^= num
set_bit = xor & (-xor)
num1 = 0
num2 = 0
for num in arr:
if num & set_bit:
num1 ^= num
else:
num2 ^= num
print(sorted([num1, num2]))

B. xor = 0
for num in arr:
xor ^= num
set_bit = xor | (xor - 1)
num1 = 0
num2 = 0
for num in arr:
if num & set_bit:
num1 ^= num
else:
num2 ^= num
print(sorted([num1, num2]))

C. xor = arr[0]
for num in arr[1:]:
xor ^= num
set_bit = xor & ~(xor - 1)
num1 = 0
num2 = 0
for num in arr:
if (num & set_bit) == 0:
num1 ^= num
else:
num2 ^= num
print(sorted([num1, num2]))

D. xor = 0
for num in arr:
xor ^= num
set_bit = xor & ~(xor + 1)
num1 = 0
num2 = 0
for num in arr:
if (num & set_bit) != 0:
num1 ^= num
else:
num2 ^= num
print(sorted([num1, num2]))

Solution

1. Step 1: Calculate XOR of all elements

   xor accumulates XOR of all elements, isolating XOR of two unique numbers.

2. Step 2: Find rightmost set bit correctly

   set_bit = xor & (-xor) correctly isolates the rightmost set bit for partitioning.

3. Step 3: Partition elements and XOR separately

   Elements are split by set_bit and XORed to find the two unique numbers.

4. Step 4: Sort and print unique elements

   Sorting ensures output is in ascending order as required.

5. Final Answer:

   Code in option A correctly finds and prints [30, 40] -> Option A

6. Quick Check:

   Rightmost set bit with xor & (-xor) + partition = correct [OK]

Hint: Use xor & (-xor) to find set bit and partition array [OK]

Common Mistakes:

• Using incorrect set_bit calculation like xor | (xor - 1)
• Wrong initialization of xor variable
• Incorrect condition in partition if statement