Two Non Repeating Elements in Array Using XOR in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of XOR-based two unique elements finder

What is the output of the following Python code that finds two non-repeating elements in an array using XOR?

DSA Python

def find_two_unique(arr):
    xor_all = 0
    for num in arr:
        xor_all ^= num
    set_bit = xor_all & (-xor_all)
    num1 = 0
    num2 = 0
    for num in arr:
        if num & set_bit:
            num1 ^= num
        else:
            num2 ^= num
    return num1, num2

result = find_two_unique([2, 3, 7, 9, 2, 3])
print(result)

A (7, 9)

B (9, 7)

C (2, 3)

D (0, 0)

💡 Hint

Remember XOR of two same numbers is zero and XOR of all elements gives XOR of unique elements.

The code uses XOR to find the XOR of the two unique numbers (7 and 9). Then it finds a set bit to separate numbers into two groups and XORs them separately to get the unique numbers. The order returned is (7, 9).

❓ Predict Output

intermediate

Output of XOR partitioning step

What is the value of 'set_bit' after executing this code snippet?

DSA Python

arr = [4, 1, 2, 1, 2, 5]
xor_all = 0
for num in arr:
    xor_all ^= num
set_bit = xor_all & (-xor_all)
print(set_bit)

A 0

B 4

C 5

D 1

💡 Hint

The set_bit isolates the rightmost set bit of xor_all.

xor_all is XOR of all elements: 4^1^2^1^2^5 = 4^0^0^5 = 1 (since pairs cancel out). The rightmost set bit of 1 is 1 itself.

🔧 Debug

advanced

Identify the error in XOR two unique elements code

What error will this code produce when run?

DSA Python

def find_two_unique(arr):
    xor_all = 0
    for num in arr:
        xor_all ^= num
    set_bit = xor_all & (-xor_all)
    num1 = 0
    num2 = 0
    for num in arr:
        if num & set_bit:
            num1 ^= num
        else:
            num2 ^= num
    return num1, num2

print(find_two_unique([1, 2, 1, 3]))

A No error, outputs (2, 3)

B TypeError

C SyntaxError

D IndexError

💡 Hint

Check the for loop syntax carefully.

The for loop is missing a colon after 'for num in arr', causing a SyntaxError.

❓ Predict Output

advanced

Output of XOR unique elements with negative numbers

What is the output of this code that finds two unique elements in an array containing negative numbers?

DSA Python

def find_two_unique(arr):
    xor_all = 0
    for num in arr:
        xor_all ^= num
    set_bit = xor_all & (-xor_all)
    num1 = 0
    num2 = 0
    for num in arr:
        if num & set_bit:
            num1 ^= num
        else:
            num2 ^= num
    return num1, num2

result = find_two_unique([-1, -2, -1, -3, -2, -4])
print(result)

A (-4, -3)

B (-3, -4)

C (-1, -2)

D (0, 0)

💡 Hint

XOR works with negative numbers as well.

The unique elements are -3 and -4. The function returns them in the order (-3, -4).

🚀 Application

expert

Number of items in dictionary after XOR grouping

After running the following code, how many keys will the dictionary 'groups' contain?

DSA Python

arr = [10, 12, 10, 15, 12, 20]
xor_all = 0
for num in arr:
    xor_all ^= num
set_bit = xor_all & (-xor_all)
groups = {}
for num in arr:
    key = 'group1' if num & set_bit else 'group2'
    groups[key] = groups.get(key, 0) + 1
print(len(groups))

A 2

B 1

C 0

D 3

💡 Hint

There are two groups based on the set bit.

The dictionary 'groups' will have two keys: 'group1' and 'group2', so length is 2.

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