Amazon Interview Question
SDE-2sCountry: India
Interview Type: In-Person
Hi,
I understand from the description of the problem that we need to return the first
integer that is not possible to obtain by summing different elements in the array;
I suppose that this integer must be at least larger than the smallest element in the
array, otherwise the solution will be just return 1 if the minimum element is larger
than 1. Also, I assume this number cannot be a number contained in the array.
Example 1:
Input array: [3, 2, 2, 2, 9]
Minimum int that is not sum: 8
Example 2:
Input array: [6, 1, 2, 7, 5]
Minimum int that is not sum: 4
Example 3:
Input array: [1, 2, 3, 2]
Minimum int that is not sum: 9
Example 4:
Input array: [8, 9, 3, 1, 1]
Minimum int that is not sum: 6
Example 5:
Input array: [2, 3, 4, 5, 8]
Minimum int that is not sum: 21
To obtain the minimum integer that cannot be formed from the sum of numbers of the array
I generate the powerset of the elements in the array, than compute the sum for each powerset
excluding the empty set; finally I scan the set of the sums of every set in the powerset,
and the minimum int that is not formed by the sum of the element of the array will be the first
missing int in the set of sums (ordered using a TreeSet). If no element is missing in the sequence
the minimum int that cannot be formed will be the maximum sum plus 1;
The time complexity will be O(2^n), time needed to compute all the sets in the powerset.
Here is my code, you can use genList(int n, int range) to generate a random list of n numbers
between 1 and range; int minNotSum(List<Integer> l) will retrieve the minimum number not formed by a sum,
Set<List<Integer>> powerSet(List<Integer> originalSet) computes the powerSet,
Set<Integer> sums(Set<List<Integer>> sets) computes the set of all the possible sums,
int computeSum(List<Integer> l) compute the sum of a single list:
import java.util.*;
public class MinIntNotSum {
public static Set<List<Integer>> powerSet(List<Integer> originalSet){
Set<List<Integer>> sets = new HashSet<List<Integer>>();
if(originalSet.size()==0) {
sets.add(originalSet);
return sets;
}
int head = originalSet.get(0);
List<Integer> rest = originalSet.subList(1, originalSet.size());
for(List<Integer> s: powerSet(rest)) {
List<Integer> newSet = new ArrayList<Integer>();
newSet.add(head);
newSet.addAll(s);
sets.add(newSet);
sets.add(s);
}
return sets;
}
public static List<Integer> genList(int n,int range) {
List<Integer> l = new ArrayList<Integer>();
Random r = new Random();
for(int i=0;i<n;i++) {
l.add(r.nextInt(range)+1);
}
return l;
}
public static Set<Integer> sums(Set<List<Integer>> sets) {
if(sets==null || sets.size()==0) {
return new TreeSet<Integer>();
}
Set<Integer> sums = new TreeSet<Integer>();
for(List<Integer> l:sets) {
if(l.size()>0)
sums.add(computeSum(l));
}
return sums;
}
public static int computeSum(List<Integer> l) {
int sum = 0;
for(Integer i: l) {
sum+=i;
}
return sum;
}
public static int minNotSum(List<Integer> l) {
if(l==null || l.size()==0) {
return -1;
}
Set<List<Integer>> ps = powerSet(l);
Set<Integer> sums = sums(ps);
List<Integer> lsums = new ArrayList<Integer>(sums);
//System.out.println("List from TreeSet:\n"+lsums);
for(int i=0;i<lsums.size()-1;i++) {
if(lsums.get(i)+1!=lsums.get(i+1)) {
return lsums.get(i)+1;
}
}
return lsums.get(lsums.size()-1)+1;
}
public static void main(String[] args) {
List<Integer> l = genList(5,10);
/*l = new ArrayList<Integer>();
l.add(4);
l.add(4);
l.add(3);
l.add(2);
l.add(4);
*/
System.out.println(l);
/*
Set<List<Integer>> ps = powerSet(l);
for(List<Integer> ll: ps) {
System.out.println(ll);
}
System.out.println("Power Sets: "+ps.size());
*/
int min = minNotSum(l);
System.out.println("Min not Sum: "+min);
}
}
First sort them.
Them calculate cumulative sum.
If some element a[i] is greater than sum + 1 then there is a gap between them. So number sum + 1 cannot be formed - this is the answer.
Sort the array and return the minimum element. If there are negative integers in the input array, this won't work. But the question says "Given an array of positive Integers"..
The way the question is worded it does sound like you just need to find the smallest number. So you don't even need to sort the array (O(nlogn). Just find the smallest element (O(n))..
The question is about the SUM of the elements in the array. So if you have an array [1,2,3] you can form sums 1,2,3,5,6 making 4 the sought element, so your answer is wrong
How exactly [1,2,3] became part of the SUM. If the elements are [1,2,3] then the sums should be [3,4,5] right? There is no missing element?
So, your example may be wrong here.
But with another example [1,3,4] then the SUM could be [4,5,7]. In this example 6 is missing..
iterate each number at array, let x is a[i], lets do swap(a[x], x) (we should use swap if x less then length of array else continue)
after that lets look throw our array and if a[x] != x return x
int findNumber (vector <int> a)
{
for (int i = 0; i < a.size(); i++) {
int x = a[i];
if (x > a.size()) continue;
swap(a[x - 1], x);
}
for (int i = 0; i < a.size(); i++) {
if (a[i] != i + 1) return i + 1;
}
return a.size();
}
I don't understand if the question is worded correctly or not, the question says to find "any" smallest positive integer that can not be formed from the sum of numbers from array.
Now let's twist the question a little bit, what is the smallest positive integer ? 0. Is there an array containing only positive integers which can have a sum less than 0 ? No because it needs to have negative numbers then.
So shouldn't the answer always be zero.
Assuming that the question allows numbers to be used multiple times
You could attempt a brute force search. This search would ultimately be very, very slow because you'd have to effectively decide whether a given number should be in the sum or not. This can also be sped up by using caching of previously computed summations.
public static boolean canBeSummed(int[] arr, int k){
if(arr == null){
throw new NullPointerException();
}
if(k < 0){
throw new IllegalArgumentException();
}
HashSet<Integer> cache = new HashSet<Integer>();
Stack<Integer> stack = new Stack<Integer>();
stack.put(0);
cache.add(0);
while(!stack.isEmpty()){
int val = stack.pop();
if(this.cache.contains(k - val){
return true;
}
else{
for(Integer i : cache){
int sum = val + i;
if(sum < this.k){
if(!this.cache.contains(sum)){
this.cache.add(sum);
stack.add(sum);
}
}
}
}
}
return false;
}
If each number can only be used once, then the computation could change significantly. I haven't implemented caching here, but it could potentially be implemented. Complexity is O(2^n):
public static boolean canBeSummed(int[] arr, int k){
if(arr == null){
throw new NullPointerException();
}
if(k < 0){
throw new IllegalArgumentException();
}
Worker worker = new Worker(arr, k);
return worker.execute();
}
static class Worker{
int[] arr;
int k;
int index;
int sum;
Worker(int[] arr, int k){
this.arr = arr;
this.k = k;
this.index = 0;
this.sum = 0;
}
boolean execute();
return executeRecur(0, 0);
}
boolean executeRecur(){
if(this.sum == k){
return true;
}
if(this.index == this.arr.length){
return false;
}
int val = this.arr[this.index];
this.index++;
if(executeRecur()){
return true;
}
this.sum += val;
if(executeRecur()){
return true;
}
this.sum -= val;
this.index--;
return false;
}
}
Assuming that "sum of numbers from array" means this positive integer cannot be one of the numbers in the array nor the sum of any of them. Then I am going to create a set that contains all possible sums from the array. If the array has n elements then the set can potentially contain as much as 2^n of them. After that, I will just keep checking which smallest positive integer doesn't exist in this set.
def smallest_missing(arr):
sums = {0}
for i in arr:
sums |= {i+x for x in sums}
i = 1
while(i in sums):
i+=1
return i
print smallest_missing([1,2,3])
This can be solved rather efficiently with dynamic programming.
public int minNotFormable(int[] input) {
Arrays.sort(input); // O(log n) black-box
boolean[] memo = new boolean[1000];
memo[0] = true; // base case
for (int num : input) {
for (int i = 0; i < memo.length - num; i++) {
memo[i + num] = true && memo[i];
}
}
// table complete; get the best result out of it
for (int i = 0; i < memo.length; i++) {
if (!memo[i]) {
return i;
}
}
return -1;
The essence of the solution is that we create a memo with some number of boolean variables representing whether we can get to that value. We then iterate through the sorted list and update the memo table accordingly.
We could add a number of heuristics here to make the procedure complete sooner should it be necessary.
We can consider some simple cases.
1. If the smallest number in array is greater than 1 then we can simply report 1 as answer.
2. If this is not the case , then sort the array.
After sorting we can apply more simple cases.
like if our sorted array is
[1 3 4 5] -- so we know that 2 cannot be formed using sum
[1 2 4 9] -- so we know that 8 cannot be formed using sum
so if sum of array A[1- (n-1) ] is smaller than A[n] , then we can report SUM( A[1 - (n-1) ] as answer.
If we complete the complete traversal of array and we could find and answer, we can report SUM(A[1 - n] ) as answer.
Here's the solution with a bit of memory conservation:
private class TempSum
{
public int Sum;
public int MaxUsed;
public TempSum(int sum, int maxUsed)
{
Sum = sum;
MaxUsed = maxUsed;
}
}
public int ArraySumMinInt(params int[] ar)
{
Array.Sort(ar);
int n = ar.Length;
var queue = new List<TempSum> { new TempSum(0, -1) };
int seekingFor = 1;
while (queue.Any())
{
var current = queue[0];
if (current.Sum > seekingFor) return seekingFor;
queue.RemoveAt(0);
int j = queue.Count - 1;
for (int i = n - 1; i > current.MaxUsed; i--)
{
var next = new TempSum(current.Sum + ar[i], i);
while (j >= 0 && queue[j].Sum > next.Sum) j--;
if (++j < queue.Count) queue.Insert(j--, next);
else
{
queue.Add(next);
j--;
}
}
seekingFor = current.Sum + 1;
}
return seekingFor;
}
The idea is to try to build all possible sums in an increasing way. Each time we take the current smallest sum we add all possible sums, which can be created by adding one of the numbers not used in it (their indices must be greater than the greatest index used before to avoid repeating, that's why the MaxUsed field is introduced). The resulting new sums must be placed in the queue in the way that keeps the queue increasing. I guess this solution has elements of dynamical programming.
In the worst case scenario (the minimum number is the sum of all elements + 1) this algorithm has the complexity O(n*2^n) (the same as bruteforce), while memory comsumption is O(combination(n,n/2)), which is better compared to bruteforce's O(2^n).
In the best case scenario (when there's no 1 in the input array) the answer will be given at once.
bool existSum(int sortedA[], int n, int sum){
int i=0, j=n-1;
while(i<j){
int mid = ((i + j)>>1);
if(sortedA[mid]>sum)
j = mid-1;
else
i = mid+1;
}
i = 0;
while(i<j){
if(sortedA[i]+sortedA[j] == sum)
return true;
if(sortedA[i]+sortedA[j] > sum)
j--;
else
i++;
}
return false;
}
int MinIntNotSum(int A[], int n){
if(A==nullptr || n<1) return 0;
sort(A, A+n); //O(nlgn)
int minSum = A[0]+A[1];
while(existSum(A,n,minSum))
minSum++;
return minSum;
}
In order to find the smallest no which can't be formed by sum of numbers of a positive array.
If we sort the array then if we add the 1st two no ,its possible smallest no can be formed.
So the array 1st element -1 would be smallest no which can't be formed.
To find this element,we can do in O(n),as really dont need to sort it.
min = a[0]
for i =1 to i <n
if a[i] < min
min = a[i]
At the end of loop min will contain the minimum value.
SO we need to find out the smallest positive integer that can not be formed from the sum of numbers from array​. Now from that we can infer that the number should also be not present in the array unless it is mandatory to add at least two numbers.
E.g. 1,2,4,8,16,32,66,69,80
Here if you see the number is 64
So going with the above assumption, we :
first will sort the array and find out the smallest missing number lets say x.
second we will get the sub set lets call it A of numbers smaller than x
perform apply the sub set sum algorithm in order to find if obtaining x is possible.
Time Complexity = Sum(x*(Number of elements in the subset A)) x start from 0 and can run till the last input in the sorted array (worst case)
public static int smallestNonSum(int[] array)
{
Set<Integer> sums = new HashSet<>();
buildSums(array, sums, 0, 0);
int i = 1;
while (sums.contains(i))
{
i++;
}
return i;
}
private static void buildSums(int[] array, Set<Integer> sums, int sumSoFar, int i)
{
if (i == array.length)
{
sums.add(sumSoFar);
}
else
{
buildSums(array, sums, sumSoFar, i + 1);
buildSums(array, sums, sumSoFar + array[i], i + 1);
}
}
public static void Execute()
{
int[] arr = { 1, 2, 4, 7, 7, 26};
Console.WriteLine(Func(arr, 0, 1));
}
public static int Func(int[] arr, int index, int k)
{
if(index >= arr.Length)
{
return k;
}
if (arr[index] > k)
{
return k;
}
int pivot = arr[index];
int t = k;
for(int i=k-pivot;i<=k-1;i++)
{
if (t == i + pivot)
{
t++;
}
else if (i + pivot > t)
{
return t;
}
}
return Func(arr, index + 1, t);
}
A detailed explanation of this algorithm is provided here:
"ELI5: Find the smallest positive integer value that cannot be represented as sum of any subset of a given array" on
medium<dot>com/dexters-lab/eli5-find-the-smallest-positive-integer-value-that-cannot-be-represented-as-sum-of-any-subset-of-f8ea2488184b
It's an NP-complete problem to decide the language of SUBSET-SUM.
- dabuja December 08, 2014