Bird
0
0
DSA Cprogramming~5 mins

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

Choose your learning style9 modes available
LearnWhyDeepVisualTryChallengeProjectRecallTime
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.
Click to reveal answer
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.
Click to reveal answer
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.
Click to reveal answer
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.
Click to reveal answer
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.
Click to reveal answer
What does XOR of all elements in an array with exactly two unique elements and others repeating give?
ASum of all elements
BXOR of the two unique elements
CZero
DProduct of the two unique elements
How do you find a bit that differs between the two unique elements after XOR?
AFind rightmost set bit using (xor & -xor)
BFind leftmost set bit using (xor | -xor)
CCount number of set bits
DUse bitwise AND of all elements
Why do we divide elements into two groups based on the set bit?
ATo find the maximum element
BTo sort the array
CTo separate the two unique elements into different groups
DTo count duplicates
What is the time complexity of the XOR method to find two unique elements?
AO(1)
BO(n^2)
CO(log n)
DO(n)
What is the XOR of a number with itself?
A0
BThe number itself
C1
DUndefined
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.
You got /4 concepts.
    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.
    You got /4 concepts.