Two Non Repeating Elements in Array Using XOR in DSA Python - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to find the XOR of all elements in the array.

DSA Python

def find_xor(arr):
    result = 0
    for num in arr:
        result = result [1] num
    return result

arr = [2, 3, 7, 9, 2, 3, 9, 11]
print(find_xor(arr))

Drag options to blanks, or click blank then click option'

A^

B+

C&

D|

Attempts:

3 left

💡 Hint

Common Mistakes

Using addition instead of XOR.

Using bitwise AND or OR instead of XOR.

The XOR operator ^ is used to find the XOR of two numbers. Here, we XOR all elements to get the XOR of the two unique numbers.

2fill in blank

medium

Complete the code to find the rightmost set bit in the XOR result.

DSA Python

def rightmost_set_bit(xor_result):
    return xor_result & -[1]

xor_result = 12
print(rightmost_set_bit(xor_result))

Drag options to blanks, or click blank then click option'

Axor_result

B1

C0

D2

Attempts:

3 left

💡 Hint

Common Mistakes

Using a constant like 1 instead of the variable.

Using bitwise OR instead of AND.

The expression xor_result & -xor_result isolates the rightmost set bit of xor_result.

3fill in blank

hard

Fix the error in the code to correctly separate the two unique numbers using the set bit.

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 & [1]:
            num1 ^= num
        else:
            num2 ^= num
    return num1, num2

arr = [4, 1, 2, 1, 2, 5]
print(find_two_unique(arr))

Drag options to blanks, or click blank then click option'

Anum1

Bxor_all

Cset_bit

Dnum2

Attempts:

3 left

💡 Hint

Common Mistakes

Using xor_all instead of set_bit in the if condition.

Using num1 or num2 instead of set_bit.

The variable set_bit holds the rightmost set bit used to separate the two unique numbers.

4fill in blank

hard

Fill both blanks to complete the function that returns the two unique numbers in sorted order.

DSA Python

def find_two_unique_sorted(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 & [1]:
            num1 ^= num
        else:
            num2 ^= num
    return tuple(sorted(([2], num2)))

arr = [10, 20, 10, 30]
print(find_two_unique_sorted(arr))

Drag options to blanks, or click blank then click option'

Aset_bit

Bxor_all

Cnum1

Dnum2

Attempts:

3 left

💡 Hint

Common Mistakes

Returning xor_all instead of num1.

Using xor_all in the if condition instead of set_bit.

The first blank should be set_bit to separate groups. The second blank should be num1 to return the first unique number.

5fill in blank

hard

Fill all three blanks to complete the function that finds two unique numbers using XOR and returns them sorted.

DSA Python

def two_non_repeating(arr):
    xor_all = 0
    for num in arr:
        xor_all ^= num
    set_bit = xor_all & -[1]
    num1 = 0
    num2 = 0
    for num in arr:
        if num & [2]:
            num1 ^= num
        else:
            num2 ^= num
    return tuple(sorted((num1, [3])))

arr = [1, 2, 3, 2, 1, 4]
print(two_non_repeating(arr))

Drag options to blanks, or click blank then click option'

Axor_all

Bset_bit

Cnum2

Dnum1

Attempts:

3 left

💡 Hint

Common Mistakes

Using num1 instead of num2 in the return statement.

Using set_bit instead of xor_all in the negative operation.

The first blank is xor_all to get the negative for isolating the rightmost set bit. The second blank is set_bit to separate groups. The third blank is num2 to return the second unique number.

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