Two Non Repeating Elements in Array Using XOR in DSA Go - Execution Trace

Concept Flow - Two Non Repeating Elements in Array Using XOR

Start with array

↓

Compute XOR of all elements

↓

Find rightmost set bit in XOR result

↓

Divide elements into two groups based on set bit

↓

Compute XOR separately in each group

↓

Result: two unique non-repeating elements

We first XOR all elements to get XOR of two unique numbers. Then find a set bit to split array into two groups and XOR each group to find the unique elements.

Execution Sample

DSA Go

arr := []int{2, 3, 7, 9, 2, 3}
xor := 0
for _, v := range arr {
    xor ^= v
}
setBit := xor & (-xor)
res1, res2 := 0, 0
for _, v := range arr {
    if v&setBit != 0 {
        res1 ^= v
    } else {
        res2 ^= v
    }
}

This code finds two unique non-repeating elements in an array where all other elements repeat twice.

Execution Table

Step	Operation	XOR Value	Set Bit	Group XORs (res1, res2)	Visual State
1	XOR all elements: 0 ^ 2	2	-	0, 0	[2]
2	XOR all elements: 2 ^ 3	1	-	0, 0	[2,3]
3	XOR all elements: 1 ^ 7	6	-	0, 0	[2,3,7]
4	XOR all elements: 6 ^ 9	15	-	0, 0	[2,3,7,9]
5	XOR all elements: 15 ^ 2	13	-	0, 0	[2,3,7,9,2]
6	XOR all elements: 13 ^ 3	14	-	0, 0	[2,3,7,9,2,3]
7	Find rightmost set bit of 14	14	2 (binary 10)	0, 0	[xor=14, setBit=2]
8	Group XORs: v=2, 2&2!=0 res1=0^2=2	14	2	2, 0	[res1=2, res2=0]
9	Group XORs: v=3, 3&2=2!=0 res1=2^3=1	14	2	1, 0	[res1=1, res2=0]
10	Group XORs: v=7, 7&2=2!=0 res1=1^7=6	14	2	6, 0	[res1=6, res2=0]
11	Group XORs: v=9, 9&2=0 res2=0^9=9	14	2	6, 9	[res1=6, res2=9]
12	Group XORs: v=2, 2&2=2!=0 res1=6^2=4	14	2	4, 9	[res1=4, res2=9]
13	Group XORs: v=3, 3&2=2!=0 res1=4^3=7	14	2	7, 9	[res1=7, res2=9]
14	Result: Two unique elements are 7 and 9	14	2	7, 9	[Unique elements: 7, 9]
15	Exit	-	-	-	All elements processed

💡 All elements processed and two unique non-repeating elements found.

Variable Tracker

Variable	Start	After Step 6	After Step 7	After Step 14	Final
xor	0	14	14	14	14
setBit	-	-	2	2	2
res1	0	0	0	7	7
res2	0	0	0	9	9

Key Moments - 3 Insights

Why do we find the rightmost set bit of the XOR result?

The rightmost set bit helps us divide the array into two groups where the two unique numbers differ at that bit. This is shown in execution_table step 7 where setBit=2 is found.

Why do we XOR elements separately in two groups?

Because the two unique numbers differ at the set bit, grouping elements by that bit ensures each unique number is isolated in one group. XORing each group cancels duplicates and leaves the unique number, as seen in steps 8-13.

Why does XOR of all elements give XOR of two unique numbers?

Pairs of repeating elements cancel out because x ^ x = 0. So XOR of all elements leaves XOR of only the two unique numbers, shown in steps 1-6.

Visual Quiz - 3 Questions

Look at the execution_table at step 7, what is the value of setBit?

A 1

B 2

C 4

D 8

💡 Hint

Check the 'Set Bit' column at step 7 in execution_table.

At which step does res2 first get a non-zero value?

A Step 11

B Step 10

C Step 9

D Step 12

💡 Hint

Look at 'Group XORs' column in execution_table rows 8-13.

If the array had no repeating elements, how would the XOR after step 6 change?

A It would be equal to the first element

B It would be zero

C It would be XOR of all unique elements

D It would be negative

💡 Hint

Refer to variable_tracker 'xor' value after step 6 and the explanation in key_moments.

Concept Snapshot

Two Non Repeating Elements Using XOR:
1. XOR all elements to get xor = a ^ b (two unique numbers).
2. Find rightmost set bit in xor to differentiate a and b.
3. Divide elements into two groups by this bit.
4. XOR each group separately to find the unique elements.
5. Time: O(n), Space: O(1).

Full Transcript

This concept finds two unique non-repeating elements in an array where all other elements repeat twice. First, XOR all elements to get xor of the two unique numbers. Then find the rightmost set bit in this xor to split the array into two groups. Each group contains one unique number and duplicates. XORing each group separately cancels duplicates and reveals the unique numbers. The execution table shows step-by-step XOR calculations and grouping. Variable tracker shows how xor, setBit, and group XORs change. Key moments clarify why the set bit is used and how grouping isolates unique numbers. The visual quiz tests understanding of key steps and variable values. This method runs in linear time and constant 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