3 ms·
This is the solution I posted there: Called the missing number m, duplicate d. The main idea is to find m+d and m-d. Then it’s trivial to find m and d. 1) Fi
by biobot 15y ago
This is the solution I posted there:
Called the missing number m, duplicate d.
The main idea is to find m+d and m-d. Then it’s trivial to find m and d.
1) Find n XOR d:
X_array = 1;
I_array = 1;
for (i=2..N)
X_array = X_array XOR A[i]; I_array = I_array XOR i;
endfor
Then m XOR d = I_array XOR X_array
2) Find m – d
It will be a little bit more complicated. The idea is to get the sum of (1..N) subtract the sum of our array. But we have to be careful not to over or underflow the result.
Diff = 0;
i = j = 0; // i index I, j index A
while (i < N) && (j < N)
if (Diff + i < N-1)
Diff = Diff + i;
i++; //consume one in I
else
Diff = Diff – A[j];
j++; // consume one in J
endif
end
// Need some corner case check here to but I will omit
3) So we have (m XOR d) and m – d. Also, note that m XOR d is basically m + d without the carry bit so it will be trivial to get m and d.
running time : 3 N <- can be squeeze to 2N if merge the two logic
space : O(1)
- pedrocr 15y ago>note that m XOR d is basically m + d without the carry bit This isn't true. XOR is addition without any carry bits so there are several solutions that have the same XOR and difference
- biobot 15y agoThere are at most 2 solutions: if m XOR d = a then either m+d = a or m+d = a+N. With the combination of m-d = b, you will find m and d. If both of them satisfied ( remember m and d are bounded by 1 and N) then we actually have two solutions.
- deleted 15y ago[deleted]
- pedrocr 15y agoHere's a counterexample. Sequence is [1, 2, 3, 4, 6, 6, 7, 8, 9, 10] so m = 5 and d = 6 diff = 5-6 = -1 xor = 5^6 = 3 1-2 = -1 1^2 = 3 5-6 = -1 5^6 = 3 9-10 = -1 9^10 = 3 So three different combinations, within N, that obey the two constraints
- biobot 15y agoMake sense! That fails my solution!
- biobot 15y agoOK. I think I find a way around. Assume d XOR m = a. Find k = position of the first bit (from MSB to LSB) in a. Then d + m can be in [a + 2^(k+1),a + 2^(k+2),...,a + 2^63]. We will have less than 63 cases. In each case, after we find d and m, make sure they are in range and then linear test. So in the end, we may need to run at most 63+3 = 66 N. But it still linear though.