This problem was asked to me in Amazon interview -
Given a array of positive integers, you have to find the smallest positive integer that can not be formed from the sum of numbers from array.
Example:
Array:[4 13 2 3 1]
result= 11 { Since 11 was smallest positive number which can not be formed from the given array elements }
What i did was :
But this was nlog(n) solution.
Interviewer was not satisfied with this and asked a solution in less than O(n log n) time.
There's a beautiful algorithm for solving this problem in time O(n + Sort), where Sort is the amount of time required to sort the input array.
The idea behind the algorithm is to sort the array and then ask the following question: what is the smallest positive integer you cannot make using the first k elements of the array? You then scan forward through the array from left to right, updating your answer to this question, until you find the smallest number you can't make.
Here's how it works. Initially, the smallest number you can't make is 1. Then, going from left to right, do the following:
candidate
) and are now looking at value A[k]
. The number candidate - A[k]
therefore must be some number that you can indeed make with the first k elements of the array, since otherwise candidate - A[k]
would be a smaller number than the smallest number you allegedly can't make with the first k numbers in the array. Moreover, you can make any number in the range candidate
to candidate + A[k]
, inclusive, because you can start with any number in the range from 1 to A[k]
, inclusive, and then add candidate - 1
to it. Therefore, set candidate
to candidate + A[k]
and increment k
.In pseudocode:
Sort(A)
candidate = 1
for i from 1 to length(A):
if A[i] > candidate: return candidate
else: candidate = candidate + A[i]
return candidate
Here's a test run on [4, 13, 2, 1, 3]
. Sort the array to get [1, 2, 3, 4, 13]
. Then, set candidate
to 1. We then do the following:
candidate
= 1:
candidate
, so set candidate = candidate + A[1] = 2
candidate
= 2:
candidate
, so set candidate = candidate + A[2] = 4
candidate
= 4:
candidate
, so set candidate = candidate + A[3] = 7
candidate
= 7:
candidate
, so set candidate = candidate + A[4] = 11
candidate
= 11:
candidate
, so return candidate
(11).So the answer is 11.
The runtime here is O(n + Sort) because outside of sorting, the runtime is O(n). You can clearly sort in O(n log n) time using heapsort, and if you know some upper bound on the numbers you can sort in time O(n log U) (where U is the maximum possible number) by using radix sort. If U is a fixed constant, (say, 109), then radix sort runs in time O(n) and this entire algorithm then runs in time O(n) as well.
Hope this helps!