Earlier quoted context omitted.
you are missing the most obvious one, no? Sum both lists and take the difference, that's the missing number, since the items are guaranteed unique
overflow
Would a BigInteger sum still overflow?
That XOR Trick (2020)
111–120 of 141 posts
Re: That XOR Trick (2020)
#112One can generalize this to k missing numbers the same way as we typically do for the addition case by using finite fields: XOR is equivalent to addition over the finite field F_2^m. So, in this field, we're calculating the sum. If we have two numbers missing, we calculate the sum and sum of squares, so we know: x + y x^2 + y^2 From which we can solve for x and y. (Note all the multiplications are Galois Field multipl…
Can you explain a bit about how and why the higher powers work?
If you imagine a polynomial L(z) that's zero at all the missing numbers, you can expand the coefficients out. For example, with 2 missing numbers (x,y), you have:
L(z) = z^2 - (x+y)z + xy.
Then you solve for the roots of L, either using your finite field's variant of the quadratic formula, or e.g. just by trying everything in the field.
* But wait, this doesn't actually work! *
Over fields of small characteristic, such as F_2^m, you need to modify the approach and use different powers. For example, in the equations above, I divided by 2. But over F_2^m in the example shown above, you cannot divide by 2, since 2=0. In fact, you cannot solve for (x,y) at all with only x+y and x^2 + y^2, because
(x+y)^2 = x^2 + y^2 + 2xy = x^2 + y^2 + 0xy (since 2=0) = x^2 + y^2
Re: That XOR Trick (2020)
#113For calculating the XOR of 1 to n there is a closed form solution, so no need to XOR them together in a loop. (n & ((n & 1) - 1)) + ((n ^ (n >> 1)) & 1) Or a much more readable version [ n, 1, n + 1, 0 ][n % 4] which makes it clear that this function cycles through a pattern of length four. Why this works can be seen if we start with some n that is divisible by four, i.e. it has the two least significant bits clear,…
[dead]
Re: That XOR Trick (2020)
#114Earlier quoted context omitted.
overflow
Would a BigInteger sum still overflow?
It doesn't matter. Overflow is a non-issue as long as you have wrapping addition and subtraction operators, which C# does - regular `+` and `-` not inside `checked {}`. You don't need to reach for BigInteger.
Re: That XOR Trick (2020)
#115Earlier quoted context omitted.
> "You are given an array A of n - 1 integers" It's an array of integers so it fits in memory (otherwise it wouldn't be called an array). As it fits in memory, n cannot be that big. I'd still ask for more requirements, TopCoder problem style: I want to know how big n can be that the array fits in memory. I didn't know that XOR trick. My solution would be a bit arrays with n bits and two for loops: one to light each b…
You could make the problem harder with "you are given a stream of n - 1 integers". N could then be any number, unbound by available memory. That makes the problem harder which makes it more interesting, a lot of the solutions wouldn't work anymore (this isn't necessarily a good interview question though)
Even with the original formulation, the array doesn't have to fit in available memory. mmap exists.
Re: That XOR Trick (2020)
#116For calculating the XOR of 1 to n there is a closed form solution, so no need to XOR them together in a loop. (n & ((n & 1) - 1)) + ((n ^ (n >> 1)) & 1) Or a much more readable version [ n, 1, n + 1, 0 ][n % 4] which makes it clear that this function cycles through a pattern of length four. Why this works can be seen if we start with some n that is divisible by four, i.e. it has the two least significant bits clear,…
Nice!
My offhand solution not using xor is to subtract from the sum of 1 to n, which has a closed form solution. The closed form roughly halves the execution time, as we only have to iterate over the range once.
Good to know there's a similar speedup available on the xor path...
Re: That XOR Trick (2020)
#117This was a go to interview question to be solved in C# at a place I worked at a while back which had developers allocated to projects working on pretty standard line of business systems. The XOR solution was a valid answer, but not the only answer we would have happily accepted. The interview question was chosen such that it's very easy to understand and quick to solve, meaning it would indicate the candidate knew at…
> "You are given an array A of n - 1 integers" It's an array of integers so it fits in memory (otherwise it wouldn't be called an array). As it fits in memory, n cannot be that big. I'd still ask for more requirements, TopCoder problem style: I want to know how big n can be that the array fits in memory. I didn't know that XOR trick. My solution would be a bit arrays with n bits and two for loops: one to light each b…
In our case we gave the list of numbers for the input which was around a dozen so memory was not a concern, again keeping the problem pretty simple.
Re: That XOR Trick (2020)
#118One can generalize this to k missing numbers the same way as we typically do for the addition case by using finite fields: XOR is equivalent to addition over the finite field F_2^m. So, in this field, we're calculating the sum. If we have two numbers missing, we calculate the sum and sum of squares, so we know: x + y x^2 + y^2 From which we can solve for x and y. (Note all the multiplications are Galois Field multipl…
This will depend on the field, and for F_2^m you want odd powers: sum(x), sum(x^3), sum(x^5) etc. Using sum(x^2) won't help because squaring over F_2^m is a field homomorphism, meaning that sum(x^2) = sum(x)^2. This is also how BCH error-correction codes work (see https://en.wikipedia.org/wiki/BCH_code ): a valid BCH codeword has sum(x^i where bit x is set in the codeword) = 0 for t odd powers i=1,3,5, ... Then if so…
Good catch, thank you!
Re: That XOR Trick (2020)
#119Adding to some other comments in the thread: finding missing or extra numbers is closely related to error-correcting codes, especially binary linear codes. In an error-correcting code, you have a string of bits or symbols, with symbol x_i appearing at position i. You choose the code so that valid sequences have a certain mathematical property, and then if one or a few symbols are corrupted, then you can use that property to correct the errors. The property is typically that a certain linear function called the "syndrome" is zero, meaning that sum(x_i * G_i) = 0 where each G_i is some strategically chosen vector, particular to the code. The math for how to correct is particular to the chosen G_i, and it's a really interesting field of study.
In a typical error-correcting code usage, you have an encoder which takes your message, and adds some extra symbols at the end which are calculated so that the syndrome is zero. Then when receiving your message, the receiver calculates the syndrome and if it's not zero, they know that at least one error has occurred. By using the code's decoding algorithm, they can figure out the fewest (and thus hopefully most likely) number of changes which would result in that error syndrome, and use this information to (hopefully) correct the transmission error.
For the missing numbers problem, you can set x_i to "how many times does the number i appear?". Then since the syndrome is sum(x_i * G_i), you can compute the syndrome on an unordered list of the i's. You are expecting the syndrome to be the same as the syndrome of full set 1...n, so when it is not, you can figure out which few x_i's are wrong that would lead to the syndrome you observed. You have an advantage because you know how many numbers are missing, but it's only a slight one.
The author's solution is called the Hamming code: you set F(i) = i, and you do the additions by xoring. Using error-correcting codes generalize to more missing numbers as well, including using xor, but the math becomes more complicated: you would want to use a fancier code such as a BCH or Goppa code. These also use xor, but in more complicated ways.
Re: That XOR Trick (2020)
#120Earlier quoted context omitted.
> Ah, my least favorite technical interview question. The epitome of turning technical interviews into a trivia contest to make them feel smart. Because isn't that the point of a tech interview?
In what way is that question trivia? I believe you under-estimate what a good interviewer is trying to do with questions such as these: Either you've seen the trick before and you get an opportunity to show the interviewer that you're an honest person by telling him you have. Huge plus and the interview can move on to other topics. Either you haven't and you can demonstrate to the interviewer your analytical skills b…
I knew a guy who would ask the binary search question in interviews (i.e. "you have an array of sorted values, what's the fastest way to find if an element is in the array?"). I always felt like this was an unfair question to ask somebody as well - it doesn't seem like something you'd be able to come up with on your own if you hadn't seen it _in an interview situation_. OTOH it's a quick way to screen people who actually did a CS degree.