Dieses Problem wurde mir im Amazon Interview gestellt -

Bei einem Array positiver Ganzzahlen müssen Sie die kleinste positive Ganzzahl finden, die nicht aus der Summe der Zahlen aus dem Array gebildet werden kann.

Beispiel:

Array:[4 13 2 3 1]
result= 11 { Since 11 was smallest positive number which can not be formed from the given array elements }

Was ich getan habe war:

sortierte das Arrayberechnete die PräfixsummeDurchlaufen Sie das Summenarray und prüfen Sie, ob das nächste Element kleiner als 1 ist und größer als die Summe, d. H. A [j] <= (Summe + 1). Wenn nicht, dann wäre die Antwort Summe + 1

Aber das war nlog (n) Lösung.

Der Interviewer war damit nicht zufrieden und fragte nach einer Lösung in weniger als O (n log n) Zeit.