Here is the interview question prompt, presented for reference.
Assume we're given an unsorted array of numbers such as this:
[ 2, 5, 1, 4, 9, 6, 3, 7 ]
We are told that when this array is sorted, there is a series of
n consecutive numbers. You are given a lower bound and an upper bound for this sequence.
There is one consecutive number missing, and we need to find it.
As an example, look at the below example. We're told that the lower bound is
1 and the upper bound is
9. The number that's missing in the unsorted series bounded by these two number is
const arr = [ 2, 5, 1, 4, 9, 6, 3, 7 ]; const lowerBound = 1; const upperBound = 9; missingInUnsorted(arr, lowerBound, upperBound); // 8
Here's the challenge-- can you find the missing number in
O(n) time? Can you do it without sorting?
You can see the full challenge with visuals at this link.
Challenges • Asked almost 2 years ago by Alejandro Matos
This is the main discussion thread generated for Missing Number In Unsorted.
what I don't understand is the + and - difference when the formula definition is 'n(n+1)/2'
There should be some property based tests for these. Unfortunately
return 8; will solve this one.
Definitely cool trick for calculating sum of numbers of range!
First i'd like to report a small 'bug' in the python interactive solution that may cause confusion to some:
def missingInUnsorted(arr, lowerBound, upperBound):
# fill in
This is what is given, but the testcase searches for missing_in_unsorted function, so even if you write it the correct solution it won't pass.
Secondly I read the recommended solution and i couldn't understand the complexity of the answer of the Gauss trick.
for 1...n: sum = n(n+1) /2
n: is the number of elements in the list(starting from 1)
n+1: the sum of the first and the last item
Why don't we just use:
return (upperBound-lowerBound+1)*(lowerBound+upperBound)//2 - sum(arr)
(upperBound-lowerBound+1) = n (the number of elements in the list starting from lowerbound)
(lowerBound+upperBound) = (n+1)
//2 -- because n(n+1) is always an even number, we don't run into problems with our result