Started by Tony, 2007-11-19T15:07:50-06:00 (Monday)
Quote from: Jerry on 2007-11-21T21:23:45-06:00 (Wednesday)Are you referring to a bitwise XOR operation?
Quote from: Tony on 2007-11-21T02:17:52-06:00 (Wednesday)Not sure if this answers the question you are asking, but if you have a set of numbers and there is only one number missing, you can just add all the numbers together. At the same time keep track of what the largest number is that you reached. Once you are done you have a variable that holds the value of all of them added together.That part is O(n). Then you can just start subtracting each number from the total, starting with 1 to N, where N is the largest number you encountered in the array. This would mean this is O(2N + 1) but that is still O(N). So, in the end you end up with the negative of the number you skipped. So, multiply that by -1 and you have the value you skipped.
Quote from: Tony on 2007-11-21T02:17:52-06:00 (Wednesday)I have no clue how you would do it if there are multiple values missing.
Quote from: Tony on 2007-11-21T01:15:25-06:00 (Wednesday)So, the numbers are not sorted in the array first right?
Quote from: Tony on 2007-11-21T01:15:25-06:00 (Wednesday)Also, a 0 means a hole? What do you mean? There just isn't a value for that possition in the array?
Quote from: William Grim on 2007-11-22T01:11:23-06:00 (Thursday)Sorry, I don't follow you. What you said in your answer actually results in you always finding 0 as the missing number.
Quote from: Tony on 2007-11-27T10:57:23-06:00 (Tuesday)Well, I think I miss understood what you were asking. What I was saying is that if the numbers are consecutive, then you just keep track of the largest value you encountered. Also, you keep a running total of all the numbers. Then just subtract ALL the numbers up to the largest value. So, if you have numbers 1-40 and 35 was missing, you would still subtract 35, which in the end, it would give you a negative 35.