Find the Only Non Repeating Element Using XOR in DSA Go

Mental Model

XORing a number with itself cancels out to zero, so XORing all numbers leaves only the one that appears once.

Analogy: Imagine you have pairs of socks in a drawer, and one single sock without a pair. If you match and remove pairs, the leftover sock is the one without a pair.

Array: [2, 3, 2, 4, 3]
XOR process: 0 ⊕ 2 -> 2
          2 ⊕ 3 -> 1
          1 ⊕ 2 -> 3
          3 ⊕ 4 -> 7
          7 ⊕ 3 -> 4
Result: 4 (only non-repeating)

Dry Run Walkthrough

Input: array: [2, 3, 2, 4, 3]

Goal: Find the single number that does not repeat in the array

Step 1: Start with result = 0, XOR with first element 2

result = 0 ⊕ 2 = 2

Why: Initialize result with first XOR to start cancellation

Step 2: XOR result with second element 3

result = 2 ⊕ 3 = 1

Why: Combine next number to cancel duplicates later

Step 3: XOR result with third element 2

result = 1 ⊕ 2 = 3

Why: XOR with duplicate 2 cancels one 2 out

Step 4: XOR result with fourth element 4

result = 3 ⊕ 4 = 7

Why: Add new number 4 to result

Step 5: XOR result with fifth element 3

result = 7 ⊕ 3 = 4

Why: XOR with duplicate 3 cancels one 3 out, leaving 4

Result:

Final result = 4, which is the only non-repeating element

Annotated Code

DSA Go

package main

import "fmt"

func findNonRepeating(arr []int) int {
    result := 0
    for _, num := range arr {
        result ^= num // XOR current number with result to cancel duplicates
    }
    return result // result holds the single non-repeating element
}

func main() {
    arr := []int{2, 3, 2, 4, 3}
    fmt.Println(findNonRepeating(arr))
}

result := 0

initialize result to zero to start XOR accumulation

for _, num := range arr { result ^= num }

XOR each element with result to cancel duplicates

return result

return the single non-repeating element after all XORs

Output

4

Complexity Analysis

Time: O(n) because we traverse the array once to XOR all elements

Space: O(1) because we use only one variable to store XOR result

vs Alternative: Compared to using a hash map to count frequencies (O(n) time and O(n) space), XOR uses constant space and is faster in practice

Edge Cases

array with only one element

returns that element as it is the only non-repeating

DSA Go

result := 0

array where all elements except one appear twice

correctly returns the single non-repeating element

DSA Go

result ^= num

empty array

returns 0 as default since no elements to XOR

DSA Go

result := 0

When to Use This Pattern

When you see a problem asking for a single unique element among duplicates, think of XOR because it cancels pairs efficiently.

Common Mistakes

Mistake: Starting XOR result with the first element instead of zero
Fix: Initialize result to zero so XOR works correctly for all elements

Mistake: Using addition or subtraction instead of XOR
Fix: Use XOR operator because addition does not cancel duplicates

Summary

Finds the single non-repeating element in an array where all others repeat twice.

Use when you need to identify one unique number among pairs efficiently.

XORing duplicates cancels them out, leaving only the unique element.

Practice

1. What does the XOR operation do when applied between two identical numbers?

easy

A. It returns the sum of the numbers

B. It returns 0

C. It returns 1

D. It returns the number itself

Solution

1. Step 1: Understand XOR property for identical numbers

   XOR of a number with itself always results in 0 because bits cancel out.

2. Step 2: Apply this property to the question

   Since the two identical numbers cancel out, the result is 0.

3. Final Answer:

   It returns 0 -> Option B

4. Quick Check:

   n XOR n = 0 [OK]

Hint: XOR of same numbers always zeroes out [OK]

Common Mistakes:

• Thinking XOR returns the number itself
• Confusing XOR with OR operation
• Assuming XOR sums numbers

2. Which of the following Go code snippets correctly initializes a variable to store XOR results for an integer slice named nums?

easy

A. var result int = 0

B. result := []int{}

C. var result string = ""

D. result := make(map[int]int)

Solution

1. Step 1: Identify the correct type for XOR accumulation

   XOR operates on integers, so the variable must be an integer initialized to 0.

2. Step 2: Check each option

   var result int = 0 initializes an integer variable to 0, suitable for XOR operations. Others use wrong types or data structures.

3. Final Answer:

   var result int = 0 -> Option A

4. Quick Check:

   Integer zero initialization for XOR [OK]

Hint: XOR needs an integer variable initialized to zero [OK]

Common Mistakes:

• Using slice or map instead of int
• Initializing with empty string
• Not initializing variable

3. What is the output of the following Go code?

package main
import "fmt"
func main() {
 nums := []int{2, 3, 2, 4, 3}
 result := 0
 for _, num := range nums {
  result ^= num
 }
 fmt.Println(result)
}

medium

A. 2

B. 3

C. 4

D. 0

Solution

1. Step 1: XOR all elements in the slice

   Calculate XOR stepwise: 0^2=2, 2^3=1, 1^2=3, 3^4=7, 7^3=4.

2. Step 2: Identify the non-repeating element

   The final XOR result is 4, which is the only number appearing once.

3. Final Answer:

   4 -> Option C

4. Quick Check:

   XOR cancels duplicates, leaves 4 [OK]

Hint: XOR duplicates cancel, leftover is unique [OK]

Common Mistakes:

• Adding numbers instead of XOR
• Miscomputing XOR steps
• Ignoring duplicates

4. Identify the error in this Go code snippet that tries to find the only non-repeating element using XOR:

package main
import "fmt"
func main() {
 nums := []int{5, 1, 5, 2, 1}
 var result int
 for i := 0; i <= len(nums); i++ {
  result ^= nums[i]
 }
 fmt.Println(result)
}

medium

A. Loop condition should be i < len(nums), not i <= len(nums)

B. Variable 'result' should be initialized to 1 instead of 0

C. The XOR operator '^=' is invalid in Go

D. The slice 'nums' should be declared as an array

Solution

1. Step 1: Check loop boundary condition

   The loop runs from i=0 to i<=len(nums), which causes out-of-range access at i=len(nums).

2. Step 2: Correct the loop condition

   Change condition to i < len(nums) to avoid index out of range error.

3. Final Answer:

   Loop condition should be i < len(nums), not i <= len(nums) -> Option A

4. Quick Check:

   Index out of range fixed by loop condition [OK]

Hint: Loop index must be less than length, not equal [OK]

Common Mistakes:

• Using <= instead of <
• Initializing result incorrectly
• Misunderstanding XOR operator

5. Given an array where every element appears twice except one element which appears once, how can you find the unique element using XOR in Go? Consider the array nums := []int{7, 9, 7, 8, 9, 10, 10}. What is the unique element?

hard

A. 7

B. 9

C. 10

D. 8

Solution

1. Step 1: XOR all elements in the array

   Calculate XOR stepwise: 0^7=7, 7^9=14, 14^7=9, 9^8=1, 1^9=8, 8^10=2, 2^10=8.

2. Step 2: Identify the unique element

   The final XOR result is 8, which appears only once in the array.

3. Final Answer:

   8 -> Option D

4. Quick Check:

   Duplicates cancel, unique is 8 [OK]

Hint: XOR all elements; duplicates vanish, unique remains [OK]

Common Mistakes:

• Adding numbers instead of XOR
• Forgetting to initialize result to zero
• Misreading array elements