What is the best way to calculate an integer in a list?

Question

Recently I was in an interview where they asked me technical questions. One of them is how you calculated what number in the list of length n-1 is missing. The list contains every number from 1 to n, except for i, where 1 <= i <= n. The rooms were not ok. My solution was to add them all and then subtract from the calculation of numbers from 1 to n, adding 1 to n and multiply by n / 2 or (n-1) / 2, if necessary. But I realized that there is a better way to do this. What is the best solution?

Answer 1

Your answer is good enough, in my opinion.

But some people - perhaps your interlocutor - one of them - are worried about overflowing and the like. In this case, use XOR instead of adding.

To get the XOR of integers from 0 to n, just XOR combine the array indices in a loop. Given the XOR of integers from 0 to n and the XOR of the elements in the array, you simply XOR combine the two of them to get the missing element.

PS The sum of integers from 1 to n is always (n + 1) * n / 2

Answer 2

iterating through an array to calculate the sum, you can check if the number is repeated.

Answer 3

Your method is absolutely perfect. It is optimal both in space and in time. Overflow may be the only problem.

Another possible method might be to use hashSet. Create an initial hash set with values ​​1-> N. Now for each number that you see in the list, remove this value from the hash set. In the end, the value that remains in the hashSet is the missing value.

This method is O (N) in time and spatial complexity. Your method (overflow ban) was O (N) in time and O (1) complexity. The added coefficient "n" for space is the cost of overflow elimination.

Answer 4

Your solution is pretty much optimal with one change, as @Nemo indicates that the sum of integers from 1 to n is always (n+1) * n/2

It is also worth noting that your approach is multi-threaded (and can be used for very large N values), splits the array into parts, then receives the sum of each part of the array in the stream, and then adds those part of the sum. It depends on what the costs of stream processing are compared with adding numbers to the array.

If you are worried about overflows and your values ​​are always int32 (since most .Length values ​​include arrays), just save the sum as int64, the sum of all positive integer values (((long)int.MaxValue) +1L) * (int.MaxValue / 2) = 2305843007066210304 , which is still able to integrate into int64 using .MaxValue = 9223372036854775807 .

Another answer, as mentioned by others, is to XOR each element and keep running XOR, but then you need to develop a formula to get the expected final XOR in O(1) .

Most likely, the interviewer is looking to see if you understand the O(N) solution with O(1) memory (which is your answer), not array sorting, and much slower with very large N values.

To further improve your decision in the code, it would be to use a pointer to access the array, not the index value (what if your C # code would be a reasonable improvement).