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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of XOR-based Two Non Repeating Elements Finder

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

DSA Go

package main

import "fmt"

func findTwoNonRepeating(arr []int) (int, int) {
    xor := 0
    for _, v := range arr {
        xor ^= v
    }
    setBit := xor & -xor
    x, y := 0, 0
    for _, v := range arr {
        if v&setBit != 0 {
            x ^= v
        } else {
            y ^= v
        }
    }
    return x, y
}

func main() {
    arr := []int{2, 3, 7, 9, 2, 3}
    a, b := findTwoNonRepeating(arr)
    fmt.Println(a, b)
}

A 9 7

B 7 9

C 2 3

D 0 0

💡 Hint

Focus on how XOR helps isolate unique elements and how the set bit divides the array.

The XOR of all elements gives xor = 7 ^ 9. The set bit isolates one differing bit between 7 and 9. Partitioning the array by this bit and XORing each group gives the two unique numbers 7 and 9. The order is consistent with the first unique number found in the partition with the set bit.

🧠 Conceptual

intermediate

Why XOR Helps Find Two Unique Elements

Why does XOR operation help in finding two non-repeating elements in an array where all other elements repeat twice?

A Because XOR multiplies all elements to find the product of unique elements

B Because XOR adds all elements together to find the sum of unique elements

C Because XOR sorts the array to separate unique elements

D Because XOR of two identical numbers is zero, so repeating elements cancel out leaving XOR of unique elements

💡 Hint

Think about what happens when you XOR a number with itself.

XOR of a number with itself is zero, so all repeating elements cancel out. The XOR of the entire array then equals the XOR of the two unique elements, which helps in isolating them.

🔧 Debug

advanced

Identify the Bug in XOR Partitioning Step

What is the bug in this partitioning step of the code to find two unique elements? for _, v := range arr { if v & xor != 0 { x ^= v } else { y ^= v } }

DSA Go

xor := 7 ^ 9
x, y := 0, 0
for _, v := range arr {
    if v & xor != 0 {
        x ^= v
    } else {
        y ^= v
    }
}

A Variables x and y are not initialized to 1

B Using '&' operator instead of '|' operator causes syntax error

C Using 'xor' instead of 'setBit' to check the rightmost set bit causes incorrect partitioning

D Loop should iterate over indices, not values

💡 Hint

Check how the partition bit is chosen from xor.

The partitioning must use the rightmost set bit of xor (setBit = xor & -xor) to separate elements. Using xor directly checks multiple bits and partitions incorrectly.

❓ Predict Output

advanced

Output of XOR Two Unique Elements with Negative Numbers

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

DSA Go

package main

import "fmt"

func findTwoNonRepeating(arr []int) (int, int) {
    xor := 0
    for _, v := range arr {
        xor ^= v
    }
    setBit := xor & -xor
    x, y := 0, 0
    for _, v := range arr {
        if v&setBit != 0 {
            x ^= v
        } else {
            y ^= v
        }
    }
    return x, y
}

func main() {
    arr := []int{-1, -2, -1, -3, -2, -4}
    a, b := findTwoNonRepeating(arr)
    fmt.Println(a, b)
}

A -3 -4

B -4 -3

C -1 -2

D 0 0

💡 Hint

XOR works the same with negative numbers; focus on partitioning by set bit.

The code correctly finds the two unique negative numbers -3 and -4 by XOR and partitioning using the rightmost set bit.

🚀 Application

expert

Number of Items in Result After XOR Partitioning

Given an array where all elements except two appear twice, after XORing all elements and partitioning by the rightmost set bit, how many elements will be in each partition?

A Each partition contains one unique element plus some repeated elements

B One partition contains both unique elements, the other is empty

C Each partition contains only one unique element and no repeated elements

D Both partitions contain only repeated elements

💡 Hint

Consider how repeated elements are distributed based on the set bit.

Repeated elements appear twice and share the same bit pattern at the set bit, so they go to the same partition twice and cancel out. Each partition ends up with one unique element plus repeated elements that cancel out.

Practice

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

easy

A. XOR of all elements gives XOR of the two unique elements

B. XOR sorts the array to separate unique elements

C. XOR counts the frequency of each element

D. XOR removes duplicates by summing elements

Solution

1. Step 1: Understand XOR properties

   XOR of a number with itself is 0, and XOR with 0 is the number itself.

2. Step 2: Apply XOR to all elements

   XORing all elements cancels out duplicates, leaving XOR of two unique elements.

3. Final Answer:

   XOR of all elements gives XOR of the two unique elements -> Option A

4. Quick Check:

   XOR cancels duplicates, leaving unique pair XOR [OK]

Hint: XOR all elements to isolate unique pair XOR quickly [OK]

Common Mistakes:

• Thinking XOR sorts or counts elements
• Assuming XOR gives unique elements directly
• Confusing XOR with addition or subtraction

2. Which of the following Go code snippets correctly initializes the XOR variable to start finding two non-repeating elements?

easy

A. xor := nil

B. xor := 0

C. xor := 1

D. xor := []int{}

Solution

1. Step 1: Identify correct XOR initialization

   XOR operation starts with 0 because XOR with 0 returns the number itself.

2. Step 2: Check Go syntax for variable initialization

   "xor := 0" correctly initializes an integer variable for XOR operations.

3. Final Answer:

   xor := 0 -> Option B

4. Quick Check:

   Start XOR with 0 for correct accumulation [OK]

Hint: Initialize XOR with 0 to start XOR operations correctly [OK]

Common Mistakes:

• Using 1 instead of 0 for XOR start
• Trying to initialize XOR with nil or slice
• Incorrect Go syntax for variable declaration

3. What is the output of the following Go code snippet? arr := []int{2, 3, 7, 9, 2, 3, 9, 11} xor := 0 for _, v := range arr { xor ^= v } fmt.Println(xor)

medium

A. 12

B. 18

C. 0

D. 11

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, 14^9=7, 7^11=12.

2. Step 2: Verify final XOR value

   The final XOR value after processing all elements is 12.

3. Final Answer:

   12 -> Option A

4. Quick Check:

   XOR of all elements = 12 [OK]

Hint: XOR duplicates cancel; XOR unique pair remains [OK]

Common Mistakes:

• Miscomputing XOR stepwise
• Assuming XOR sums elements
• Ignoring duplicates canceling out

4. Identify the bug in this Go code snippet that tries to find two non-repeating elements using XOR: arr := []int{4, 1, 2, 1, 2, 5} xor := 0 for i := 0; i <= len(arr); i++ { xor ^= arr[i] } fmt.Println(xor)

medium

A. Use a map instead of XOR for this problem

B. XOR variable should be initialized to 1

C. Loop condition should be i < len(arr), not i <= len(arr)

D. Array elements should be converted to strings before XOR

Solution

1. Step 1: Check loop boundary

   Loop uses i <= len(arr), which causes out-of-range error because valid indices are 0 to len(arr)-1.

2. Step 2: Correct loop condition

   Change to i < len(arr) to avoid index out of range and correctly XOR all elements.

3. Final Answer:

   Loop condition should be i < len(arr), not i <= len(arr) -> Option C

4. Quick Check:

   Index out of range fixed by correct loop boundary [OK]

Hint: Use i < len(arr) to avoid index errors in loops [OK]

Common Mistakes:

• Using <= instead of < in loop condition
• Initializing XOR with wrong value
• Misunderstanding XOR usage for strings

5. Given the array arr := []int{6, 3, 5, 4, 5, 3, 4, 7}, which two numbers are the non-repeating elements found using the XOR method?

hard

A. [5, 6]

B. [3, 5]

C. [4, 7]

D. [6, 7]

Solution

1. Step 1: XOR all elements to get xorVal

   Calculate XOR: 6^3=5, 5^5=0, 0^4=4, 4^5=1, 1^3=2, 2^4=6, 6^7=1. Final xorVal = 1.

2. Step 2: Find rightmost set bit and separate elements

   Rightmost set bit in xorVal=1. Partition array into two groups based on this bit and XOR separately to find unique elements 6 and 7.

3. Final Answer:

   [6, 7] -> Option D

4. Quick Check:

   Unique elements are 6 and 7 after XOR partition [OK]

Hint: Use rightmost set bit to split and find unique elements [OK]

Common Mistakes:

• Not partitioning array by set bit
• Mixing up duplicates with unique elements
• Incorrect XOR calculations