Error in solution 12.15 (v1.4.5, page 305)

#1

I briefly restate the problem for clarity:

Let A be an array of n integers in Z_n. Every member of Z_n appears exactly once, except that t in Z_n appears twice and m in Z_n is missing from A. Find t and m in O(n) time and O(1) space.

The book provides two solutions. The first one is correct. The second solution claims to improve upon the first by addressing potential overflow issues. Barring a misunderstanding, I believe that the second solution is incorrect. For clarity, I describe the original second solution:

Compute x = m xor t. Note x is not 0.
Pick a non-zero bit in x. Call the integer represented by it h.
h must be m or t. (This is where the reasoning goes awry)
Search A for h.

This solution is incorrect because it fails when m and t each have more than one one-bit.
e.g. consider.
m = 3 = "0011"
t = 12 = “1100”

Edit: Sorry I meant t = 12, not 6. 3(011) and 6(011) do not exhibit my point because their xor (101) leaves ONE bit to represent t and m. In contrast, 3 xor 12 = ‘1111’ and now suddenly, the significant TWO bits ‘belong’ to 12 and the less significant 2 bits ‘belong’ to 3. Here, picking a single bit position is no longer sufficient.

0 Likes
#2

Hey Yi,

I got a little problem of understanding your explanation. Therefore, I tried to run a small test in the program, and following is the code snippet I use to test your test case:

vector<int> A = {0, 1, 2, 4, 5, 6, 6};
auto ans = find_duplicate_missing(A);
assert(ans.first == 6 && ans.second == 3);

You may try to run this, and see it works or not. If there is still a problem at your side, I could email you my test program (basically it is the solution with the test case.

0 Likes
#3

Sorry I made an error in my binary… I wanted 3 vs 12, rather than 3 vs 6… I edited my original post for clarity.

0 Likes
#4

I think you have some misunderstandings about after we picking a non-zero bit in x. We use the bit to find potential candidate of missing or duplicate. It is not saying that one is missing or duplicate.

After I examine the program, I still don’t see any reason why this algorithm fails. Personally I have modified the test case (with m = 3 and t = 12) and verified it by myself. I strongly recommend you to try our program with the code snippet I provided before.

0 Likes
#5

Sorry about the troubles. I double checked and you are correct. I will leave this post up in case anyone else has the same misunderstanding.

0 Likes
#6

Not a problem :slight_smile: Thanks for your efforts of reaching us to clarify your question. Please keep doing that if you encounter any question in the future.

0 Likes