[Geeks for Geeks] Smallest Positive Integer that can not be represented as Sum

Smallest Positive Integer that can not be represented as Sum

Given an array of size N, find the smallest positive integer value that cannot be represented as sum of some elements from the array.

  • Time : O(nlogn)
  • Space : O(1)
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
long long smallestpositive(vector<long long> A, int n) {
sort(begin(A), end(A));
long long res = 1;
for(int i = 0; i < n; i++) {
if(A[i] > res) return res;
res += A[i];
}
return res;
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/05/21/PS/GeeksforGeeks/smallest-positive-integer-that-can-not-be-represented-as-sum/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.