Microsoft Interview Question

Having a vector V with (N-1) numbers with values from 1 to N find the number X that is missing which value is between 1 and N.

Solution1 - Low Efficiency - O(n*n)
Take every number from 1 to N and search it if it's in the vector number.

Solution2 - O(n*logn)
Sort the number first and then check if V[i] != i.

Solution3- O(n)
Using "Divide et Impera" algorithm to split the vector in 2 sub-vectors having size of maximum N/2 (first vector will have all the elements smaller or equal with N/2 and the second vector will have all the elements bigger than N/2). After every split you can find in which sub-vector is the missing number because will have a small number of elements.

Solution4 - The Smart One- O(n) time, O(1) space
Using the property of SUM(1..N) = N*(N+1)/2, the element X that is missing can be find by:
X = SUM(1..N) - SUM(V's elements).