Community

Start a Thread
Filters
By Category
Notifications
Subscribe You’re not receiving notifications from this thread.

Missing Number In Unsorted (Main Thread)

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 8.

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?

Constraints

  • Length of the array <= 10000
  • The upper bound <= 10000
  • The lower bound >= -10000
  • Expected time complexity : O(n)
  • Expected space complexity : O(1)

You can see the full challenge with visuals at this link.

Challenges • Asked over 5 years ago by Alejandro Matos

Jake from AlgoDaily Commented on Jul 22, 2019:

This is the main discussion thread generated for Missing Number In Unsorted.

Alejandro Matos Commented on Jul 22, 2019:

what I don't understand is the + and - difference when the formula definition is 'n(n+1)/2'

Cypher1 Commented on Jul 22, 2019:

There should be some property based tests for these. Unfortunately return 8; will solve this one.

Dmitry Pavlov Commented on Jan 22, 2021:

Definitely cool trick for calculating sum of numbers of range!

ntassop@gmail.com Commented on Apr 24, 2021:

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
return

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
where,
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)

where:

(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