Book v1.4.7 problem on 12.16

#1

Hi I have a question on the 12.16 Find an element from array that appears only once(others appear 3 times)

my question is this line in your solution:

next_ones = (~i & ones) | (i & ~ones & ~twos);

I know this line is matching your explanation part “…the count was 0 modulo 3 and the j-th bit in Ai-1 is a one”.

However, I think, to match your explanation the code should be

next_ones = (~i & ones) | (i & ~ones & ~twos) | (i & ones & twos);

But to my astonishment, I found that even if you don’t add " |(i & ones & twos)", your code passes all the test cases and no bugs.

My question is
Why does next_ones = (~i & ones) | (i & ~ones & ~twos) suffice?

Thanks

0 Likes
#2

Hey Pete,

Thanks for your question, and it is surely a good question that I shall mention or explain it further in the later version.

The reason we don’t care about (i & ones & twos) because it represents threes instead of ones.

In addition, the reason why next_ones = (~i & ones) | (i & ~ones & ~twos) suffice because it shows all possible situations that how ones appear (either the situation that not showing in i and already existing in ones, or the situation that showing in i but not existing in ones and twos).

Please let me know what you think if there is anything that is not clear, and I am glad you could bring this topic which refreshes my memory of this problem.

Happy Thanksgiving!

Tsung-Hsien

0 Likes
#3

Hi Tsunghsien,

Thanks for response, after I saw your response and I thought through twice I think now I understand why it suffices. Because all the distinct value element in this problem appears no more than 3 times. Thus, there is no need to consider the situation where one appear in i and at the same time appear both in ones and twos (i & ones & twos).

0 Likes
#4

Hey Pete,

Your point is also pretty solid which I think worth of mentioning that in the later version. Thanks for this insight.

0 Likes