0
$\begingroup$

I'm having trouble figuring out why using XOR for this problem works; I've done it a couple of times by-hand, and can't really seem to understand it. I know that XOR is commutative and associative, which is why it's good for finding (missing) duplicated numbers in a list. But applying that to the following problem doesn't quite click with me:

In a non-empty array of numbers, every number appears exactly twice except two numbers that appear only once. Find the two numbers that appear only once.

Input: [1, 4, 2, 1, 3, 5, 6, 2, 3, 5]
Output: [4, 6]
Input: [2, 1, 3, 2]
Output: [1, 3]

The algorithm to find the two single numbers is this in psuedocode:

list_xor = 0
for each num in nums:
    # XORing all the numbers in the list
    list_xor = list_xor XOR num 

# find the first bit of list_xor, used for partitioning [nums] 
right_most_bit_in_list_xor = find_right_most_bit(list_xor)

!!! I don't understand this part !!!
num1, num2 = (0, 0)
for each num in nums:
    # num has a bit that's set that matches right_most
    if (right_most_bit_in_list_xor & num) == 1:
        num1 = num1 XOR num
    # else, the num doesn't have this bit set
    else:
        num2 = num2 XOR num

return num1, num2

I can't figure out why XOR'ing the right-most bit in the result from XOR'ing the list with each number in the list will result in num1 and num2 being the only single numbers.

Here's a sample "by-hand" run that I did:

Input: [1, 1, 2, 3, 2, 4], Output: [3, 4]
list_xor = 
(000^001) = 001 -> (001^001) = 000 -> (000^010) = 010
 -> (010^011) = 001 -> (001^010) = 011 -> (011^100) = 111 (7 in decimal)

Right-most bit of 7 = 001 (1 in decimal)

Numbers with 001 as a set bit: [1, 1, 3]
num1 = 000 -> (000^001) = 001 -> (001^001) = 000 -> (000^011) = 011 (3 in decimal)

Numbers with 001 NOT set as a bit: [2, 2, 4]
num2 = 000 -> (000^010) = 010 -> (010^010) = 000 -> (000^100) = 100 (4 in decimal)

From the run-through, you can see that they're partitioned into two lists with duplicates and a single, single number: [1, 1, 3] and [2, 2, 4]. But how did it partition itself just based on the right-most bit?

$\endgroup$
0

1 Answer 1

5
$\begingroup$

Let $x$ and $y$ be the numbers that appear only once and let $z_1, \dots,z_n$ be the other input numbers (each number appears twice). Then $x \oplus y \oplus z_1 \oplus \dots \oplus z_n = x \oplus y$ and, in particular, if the generic $i$-th bit in $x \oplus y$ is $1$ then exactly one between $x$ and $y$ has the $i$-th bit set to $1$.

Pick any $i$ such that the $i$-th bit of $x \oplus y$ is $1$ (in your code this is the rightmost bit, but any such bit works) and suppose without loss of generality that the $i$-th bit of $x$ is $1$ (and hence the $i$-th bit of $y$ is $0$).

Let $Z^+$ (resp. $Z^-$) the (multi-)set containing the numbers $z_1, \dots, z_n$ that have their $i$-th bit set to $1$ (resp. $0$). Since there are exactly two copies of each number in $Z^+$ (resp. $Z^-)$, we have: $$ x \oplus \left(\bigoplus_{z \in Z^+} z\right) = x \oplus 0 =x, $$ where the left-hand term is exactly how your algorithm computes num1. Similarly, $$ y \oplus \left(\bigoplus_{z \in Z^-} z\right) = y \oplus 0 = y, $$ which corresponds to num2.

$\endgroup$
5
  • $\begingroup$ That was a beyond excellent answer, thank you, Steven. $\endgroup$ Jun 10, 2022 at 23:25
  • $\begingroup$ @discreteboy Would btw be more efficient to compute y by xoring just x^y and x. $\endgroup$ Jun 10, 2022 at 23:49
  • $\begingroup$ @Steven Why are we assuming that the i'th bit is 1? In the given example, if the two singletons have the same parity, it will be 0, and the algorithm looks like it shouldn't work. $\endgroup$
    – A_P
    Jun 11, 2022 at 0:16
  • $\begingroup$ @A_P, I'm selecting an index $i$ such that the $i$-th bit of $x \oplus y \oplus z_1 \oplus \dots \oplus z_n$ is $1$. This index is not necessarily the least significant bit! Notice that there must be at least one such index $i$ because otherwise we would have $x \oplus y =0$ which would mean that $x = y$, a contradiction. $\endgroup$
    – Steven
    Jun 11, 2022 at 8:41
  • $\begingroup$ @Steven I now see the confusion. In the OP, the function "find_right_most_bit" means "find the rightmost nonzero bit," not "find the value of the least significant bit." $\endgroup$
    – A_P
    Jun 11, 2022 at 21:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.