Two Non Repeating Elements in Array Using XOR in DSA Go - 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 checking each number multiple times.

🎯 Goal: Build a Go program that finds the two unique numbers in an array where every other number repeats twice, using the XOR operation.

📋 What You'll Learn

Create an integer slice called nums with the exact values: 2, 3, 7, 9, 2, 3

Create an integer variable called xorAll to hold the XOR of all numbers

Use a for loop with variable num to XOR all elements in nums and store in xorAll

Find the rightmost set bit in xorAll and store it in rightmostSetBit

Create two integer variables num1 and num2 initialized to 0

Use a for loop with variable num to separate numbers into two groups based on rightmostSetBit and XOR them into num1 and num2

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

💡 Why This Matters

🌍 Real World

This technique is useful in error detection, data analysis, and situations where you need to find unique elements quickly without extra memory.

💼 Career

Understanding bitwise operations and efficient algorithms is important for software engineers working on performance-critical applications, embedded systems, and coding interviews.

1

Create the array of numbers

Create an integer slice called nums with these exact values: 2, 3, 7, 9, 2, 3

DSA Go

# Your code here

Hint

Use nums := []int{2, 3, 7, 9, 2, 3} to create the slice.

2

Calculate XOR of all numbers

Create an integer variable called xorAll and set it to 0. Then use a for loop with variable num to XOR all elements in nums and store the result in xorAll

DSA Go

package main

func main() {
    nums := []int{2, 3, 7, 9, 2, 3}
    // Your code here
}

Hint

Initialize xorAll to 0. Use for _, num := range nums and inside the loop do xorAll ^= num.

3

Find rightmost set bit and separate numbers

Create an integer variable called rightmostSetBit and set it to xorAll & (-xorAll). Then create two integer variables num1 and num2 initialized to 0. Use a for loop with variable num to separate numbers in nums into two groups based on rightmostSetBit. XOR numbers in the first group into num1 and in the second group into num2

DSA Go

package main

func main() {
    nums := []int{2, 3, 7, 9, 2, 3}
    xorAll := 0
    for _, num := range nums {
        xorAll ^= num
    }
    // Your code here
}

Hint

Use rightmostSetBit := xorAll & (-xorAll) to find the bit. Initialize num1, num2 := 0, 0. Loop through nums and use if num&rightmostSetBit != 0 to separate and XOR into num1 or num2.

4

Print the two unique numbers

Use fmt.Println(num1, num2) to print the two unique numbers separated by a space

DSA Go

package main

import "fmt"

func main() {
    nums := []int{2, 3, 7, 9, 2, 3}
    xorAll := 0
    for _, num := range nums {
        xorAll ^= num
    }
    rightmostSetBit := xorAll & (-xorAll)
    num1, num2 := 0, 0
    for _, num := range nums {
        if num&rightmostSetBit != 0 {
            num1 ^= num
        } else {
            num2 ^= num
        }
    }
    // Your code here
}

Hint

Use fmt.Println(num1, num2) to print the two unique numbers separated by a space.

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