Find the Only Non Repeating Element Using XOR in DSA Go - Execution Trace

Concept Flow - Find the Only Non Repeating Element Using XOR

Start with result = 0

↓

For each element in array

↓

Apply XOR: result = result XOR element

↓

Repeat for all elements

↓

Result holds the unique element

↓

Return result

We start with zero and XOR it with every element in the array. Because XOR of two same numbers is zero, all repeating elements cancel out, leaving only the unique element.

Execution Sample

DSA Go

package main

import "fmt"

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

This code finds the only non-repeating element in the array by XORing all elements.

Execution Table

Step	Operation	Current Element	Result Before XOR	Result After XOR	Visual State (XOR Result)
1	Initialize result	N/A	N/A	0	0
2	XOR with 2	2	0	2	0 ^ 2 = 2
3	XOR with 3	3	2	1	2 ^ 3 = 1
4	XOR with 5	5	1	4	1 ^ 5 = 4
5	XOR with 4	4	4	0	4 ^ 4 = 0
6	XOR with 5	5	0	5	0 ^ 5 = 5
7	XOR with 3	3	5	6	5 ^ 3 = 6
8	XOR with 4	4	6	2	6 ^ 4 = 2
9	End of array	N/A	2	2	Unique element found: 2

💡 All elements processed; repeating elements canceled out; result holds the unique element 2.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	Final
result	0	2	1	4	0	5	6	2	2
current element	N/A	2	3	5	4	5	3	4	N/A

Key Moments - 3 Insights

Why does XORing a number with itself result in zero?

Because XOR compares bits and returns 0 when bits are the same. So, any number XOR itself cancels out to zero, as shown in step 5 where 4 ^ 4 = 0.

Why do we start with result = 0?

Starting with zero is important because XOR with zero returns the number itself, so the first element sets the initial result, as seen in step 2 where 0 ^ 2 = 2.

How does XOR help find the unique element among duplicates?

Because XOR of duplicates cancels out to zero, only the unique element remains after XORing all elements, demonstrated by the final result 2 in step 9.

Visual Quiz - 3 Questions

Look at the execution table, what is the value of 'result' after XORing with the second element?

A 4

B 1

C 2

D 0

💡 Hint

Check row 3 in the execution_table where current element is 3 and result after XOR is shown.

At which step does the 'result' become zero during the XOR process?

A Step 6

B Step 4

C Step 5

D Step 8

💡 Hint

Look at the 'Result After XOR' column in the execution_table for when the value is zero.

If the array had one more '2' at the end, what would be the final 'result'?

A 0

B 2

C 4

D 6

💡 Hint

Adding another '2' would XOR the current result 2 with 2 again, check XOR properties in variable_tracker.

Concept Snapshot

Find unique element using XOR:
- Initialize result = 0
- XOR result with each array element
- Duplicates cancel out (x ^ x = 0)
- Result holds the unique element
- Time: O(n), Space: O(1)

Full Transcript

This concept uses XOR operation to find the only non-repeating element in an array. We start with a result variable set to zero. Then, for each element in the array, we XOR it with the result. Because XOR of a number with itself is zero, all duplicates cancel out. At the end, the result contains the unique element. The execution table shows each step with the current element and how the result changes. Key moments clarify why XOR works this way and why we start with zero. The visual quiz tests understanding of the XOR process and final result.

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