Good morning! Here's our prompt for today.
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
.
1const arr = [ 2, 5, 1, 4, 9, 6, 3, 7 ];
2const lowerBound = 1;
3const upperBound = 9;
4
5missingInUnsorted(arr, lowerBound, upperBound);
6// 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)
Try to solve this here or in Interactive Mode.
How do I practice this challenge?
xxxxxxxxxx
def missingInUnsorted(arr, lowerBound, upperBound):
# fill in
return
​
​
import unittest
​
​
class Test(unittest.TestCase):
def test_1(self):
assert missing_in_unsorted([2, 5, 1, 4, 9, 6, 3, 7], 1, 9) == 8
print(
"PASSED: `missing_in_unsorted([ 2, 5, 1, 4, 9, 6, 3, 7 ], 1, 9)` should return `8`"
)
​
​
if __name__ == "__main__":
unittest.main(verbosity=2)
print("Nice job, 1/1 tests passed!")
​
Here's how we would solve this problem...
How do I use this guide?
Access all course materials today
The rest of this tutorial's contents are only available for premium members. Please explore your options at the link below.