Two Non Repeating Elements in Array Using XOR in DSA C - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind using XOR to find two non-repeating elements in an array?

XOR of all elements gives XOR of the two unique elements because pairs cancel out. Then, use a set bit to separate elements into two groups to find each unique element.

beginner

Why do pairs of repeating elements cancel out when XORed together?

Because XOR of a number with itself is 0, so pairs XOR to 0 and do not affect the final XOR result.

intermediate

How do you find a set bit in the XOR of two unique elements?

Use expression (xor & -xor) to isolate the rightmost set bit, which helps to divide elements into two groups.

beginner

What is the time complexity of finding two non-repeating elements using XOR?

O(n), where n is the number of elements in the array, because we scan the array a few times linearly.

intermediate

Explain why dividing elements into two groups based on a set bit helps find the unique elements.

The two unique elements differ at that bit, so grouping by that bit separates them. XORing each group gives one unique element each.

What does XOR of all elements in an array with exactly two unique elements and others repeating give?

A Sum of all elements

B XOR of the two unique elements

C Zero

D Product of the two unique elements

Pairs cancel out in XOR, leaving XOR of the two unique elements.

How do you find a bit that differs between the two unique elements after XOR?

A Find rightmost set bit using (xor & -xor)

B Find leftmost set bit using (xor | -xor)

C Count number of set bits

D Use bitwise AND of all elements

The expression (xor & -xor) isolates the rightmost set bit.

Why do we divide elements into two groups based on the set bit?

A To find the maximum element

B To sort the array

C To separate the two unique elements into different groups

D To count duplicates

The two unique elements differ at that bit, so grouping separates them.

What is the time complexity of the XOR method to find two unique elements?

A O(1)

B O(n^2)

C O(log n)

D O(n)

The method scans the array a few times linearly, so O(n).

What is the XOR of a number with itself?

A 0

B The number itself

C 1

D Undefined

XOR of a number with itself is always 0.

Explain step-by-step how to find two non-repeating elements in an array using XOR.

Think about how XOR cancels pairs and how to separate unique elements.

Why does the XOR method work efficiently for finding two unique elements in an array where others repeat twice?

Focus on XOR properties and grouping by bit.

Practice

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

easy

A. To cancel out all repeating elements and isolate the XOR of the two unique elements

B. To sort the array in ascending order

C. To count the frequency of each element

D. To reverse the array elements

Solution

1. Step 1: Understand XOR property for duplicates

   XOR of two identical numbers is 0, so XORing all elements cancels out duplicates.

2. Step 2: Result after XORing all elements

   The result is XOR of the two unique elements because duplicates cancel out.

3. Final Answer:

   To cancel out all repeating elements and isolate the XOR of the two unique elements -> Option A

4. Quick Check:

   XOR cancels duplicates = isolate unique elements [OK]

Hint: XOR duplicates become zero, leaving unique elements XOR [OK]

Common Mistakes:

• Thinking XOR sorts the array
• Using XOR to count frequencies
• Assuming XOR reverses elements

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

easy

A. int xor = 1;

B. int xor = 0;

C. int xor = -1;

D. int xor = NULL;

Solution

1. Step 1: Understand XOR identity element

   XOR with 0 leaves the number unchanged, so start with 0.

2. Step 2: Initialize XOR variable

   Setting xor = 0 allows XORing all elements correctly.

3. Final Answer:

   int xor = 0; -> Option B

4. Quick Check:

   Start XOR with 0 for correct accumulation [OK]

Hint: Initialize XOR with 0 because 0 XOR x = x [OK]

Common Mistakes:

• Initializing XOR with 1 or -1
• Using NULL for integer variable
• Not initializing XOR variable

3. What will be the output of the following C code snippet?

int arr[] = {2, 3, 7, 9, 2, 3};
int xor = 0;
for(int i = 0; i < 6; i++) {
    xor ^= arr[i];
}
printf("%d", xor);

medium

A. 14

B. 9

C. 7

D. 0

Solution

1. Step 1: XOR all elements in the array

   Calculate 2^3=1, 1^7=6, 6^9=15, 15^2=13, 13^3=14.

2. Step 2: Result after XORing all elements

   The final XOR value is 14, which is XOR of the two unique elements 7 and 9.

3. Final Answer:

   14 -> Option A

4. Quick Check:

   XOR all elements = 14 [OK]

Hint: XOR all elements to get XOR of unique pair [OK]

Common Mistakes:

• Stopping XOR early
• Miscomputing XOR values
• Assuming output is one unique element

4. Identify the error in the following code snippet that attempts to find two non-repeating elements using XOR:

int arr[] = {4, 1, 2, 1, 2, 5};
int xor = 0;
for(int i = 0; i < 6; i++) {
    xor ^= arr[i];
}
int set_bit = xor & ~(xor - 1);
int x = 0, y = 0;
for(int i = 0; i < 6; i++) {
    if(arr[i] & set_bit)
        x ^= arr[i];
    else
        y ^= arr[i];
}
printf("%d %d", x, y);

medium

A. Incorrect calculation of set_bit using xor & ~(xor - 1)

B. Loop range should be 0 to 5, not 0 to 6

C. Missing initialization of x and y to zero

D. No error, code works correctly

Solution

1. Step 1: Check set_bit calculation

   set_bit = xor & ~(xor - 1) correctly finds rightmost set bit.

2. Step 2: Verify loops and initialization

   Loops run from 0 to 5 (6 elements), x and y initialized to 0 correctly.

3. Final Answer:

   No error, code works correctly -> Option D

4. Quick Check:

   Code logic and syntax are correct [OK]

Hint: Check bitwise operations and loop ranges carefully [OK]

Common Mistakes:

• Miscomputing set_bit
• Wrong loop boundaries
• Uninitialized variables

5. Given an array where exactly two elements appear once and all others appear twice, how can you find those two unique elements efficiently using XOR? Choose the correct sequence of steps.

hard

A. Sort the array, then scan to find unique elements

B. Use a hash map to count frequencies, then pick elements with count 1

C. XOR all elements, find rightmost set bit in XOR result, divide elements into two groups by that bit, XOR each group separately

D. XOR all elements twice to get unique elements

Solution

1. Step 1: XOR all elements to get XOR of two unique elements

   This cancels out duplicates and leaves XOR of unique pair.

2. Step 2: Find rightmost set bit in XOR result

   This bit differs between the two unique elements.

3. Step 3: Divide elements into two groups based on this bit and XOR each group

   This separates the two unique elements and finds them individually.

4. Final Answer:

   XOR all elements, find rightmost set bit in XOR result, divide elements into two groups by that bit, XOR each group separately -> Option C

5. Quick Check:

   Use XOR and bit partitioning to find unique elements [OK]

Hint: Use XOR and bit mask to split and find unique elements [OK]

Common Mistakes:

• Sorting instead of XOR
• Using hash map (extra space)
• XORing twice without grouping