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.