3 ms·

Well, if you don't want to overflow then rather than summing all the numbers first and subtracting a single time from (n(n+1) / 2) at the end, you can subtract

Well, if you don't want to overflow then rather than summing all the numbers first and subtracting a single time from (n(n+1) / 2) at the end, you can subtract numbers one at a time from 1..n and end up with the same result. In order to make sure you don't overflow you have to tend toward zero, subtracting large numbers when your running sum gets large and small ones when it's small. Here, I coded this for you - http://codepad.org/kdqoLXFA http://codepad.org/kdqoLXFA (scroll down for the output! it's not just a pastebin but runs it for you). As you can see my code contains tests at the end to show it's working, but not a robust testing class because it's a brittle piece of shit. I don't even want to know what it would do with input that doesn't meet its promises. I also Googled this and an alternative (that admittedly I did not think of) given such tight restraints is to keep a running bitwise xor of your elements, and also bitwise xor'ing in (1..n) similar to the above - then you don't need to do it from a head and a tail, at the end rather than a difference you just end up with the missing number. This is probably superior to what I just coded. But both algorithms are really stupid and really brittle. Sorting is fast and there is no reason not to do it that way.

zem 10y ago
yeah, the bitwise xor was my next solution, and what the interviewer was looking for. i found it a fun puzzle, satisfying to solve and not really brittle at all (why would you feel it was? it's just a simple loop with an xored accumulator; it cannot overflow or do anything funny). i like the idea of subtracting from either the head or the tail of a virtual list too; that's clever :)
- logicallee 10y ago
  it's really brittle for the reason that I mentioned originally: by using a more robust, correct solution, (sorting) you can check that the input is proper, and if not, raise the appropriate exception or return the appropriate error, or simply return -1 or 0 or some other signal value. At any rate you will not silently, and in a way that seemingly works, return some arbitrary value which is simply not true. (Which is the worst kind of failure.) This does not have a large cost. With the xor solution, on the other hand, you don't really have that option -- if the input does not exactly match the input condition, then it WILL return whatever - with no indication that anything is amiss. Even slightly wrong input will give unpredictable, completely wrong output with no indication that anything is wrong. What's worse is that it's trivial to game: as an exercise try making a malicious generator that takes an n of at least 4 and Target number, and returns (generates) an array (of size n-1) for feeding the XOR solution that shall get the xor solution to output the Target as the missing number. Further, the malicious generator, instead of generating an array with one missing number, actually shall generate a list which is as close to correct as possible, except that it shall (as an extra 'fuck you') in all cases contain the "Target" value -- twice. btw thanks for the feedback on the sum thing :)

zem 10y ago

yeah, the bitwise xor was my next solution, and what the interviewer was looking for. i found it a fun puzzle, satisfying to solve and not really brittle at all (why would you feel it was? it's just a simple loop with an xored accumulator; it cannot overflow or do anything funny). i like the idea of subtracting from either the head or the tail of a virtual list too; that's clever :)

logicallee 10y ago
it's really brittle for the reason that I mentioned originally: by using a more robust, correct solution, (sorting) you can check that the input is proper, and if not, raise the appropriate exception or return the appropriate error, or simply return -1 or 0 or some other signal value. At any rate you will not silently, and in a way that seemingly works, return some arbitrary value which is simply not true. (Which is the worst kind of failure.) This does not have a large cost. With the xor solution, on the other hand, you don't really have that option -- if the input does not exactly match the input condition, then it WILL return whatever - with no indication that anything is amiss. Even slightly wrong input will give unpredictable, completely wrong output with no indication that anything is wrong. What's worse is that it's trivial to game: as an exercise try making a malicious generator that takes an n of at least 4 and Target number, and returns (generates) an array (of size n-1) for feeding the XOR solution that shall get the xor solution to output the Target as the missing number. Further, the malicious generator, instead of generating an array with one missing number, actually shall generate a list which is as close to correct as possible, except that it shall (as an extra 'fuck you') in all cases contain the "Target" value -- twice. btw thanks for the feedback on the sum thing :)