Given an array of size N, find the smallest positive integer value that is either not presented in the array or cannot be represented as a sum(coz sum means you are adding two or more elements) of some elements from the array.
Example 1:
Input: 
N = 6
array[] = {1, 10, 3, 11, 6, 15}
Output: 
2
Explanation:
2 is the smallest integer value that cannot 
be represented as sum of elements from the array.
Example 2:
Input: 
N = 3
array[] = {1, 1, 1}
Output: 
4
Explanation: 
1 is present in the array. 
2 can be created by combining two 1s.
3 can be created by combining three 1s.
4 is the smallest integer value that cannot be 
represented as sum of elements from the array.
Your Task:  
You don't need to read input or print anything. Complete the function smallestpositive() which takes the array and N as input parameters and returns the smallest positive integer value that cannot be represented as the sum of some elements from the array.
Expected Time Complexity: O(N * Log(N))
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 10^{6}
1 ≤ array[i] ≤ 10^{9}
The array may contain duplicates.

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Sorting

Data structures

Mathematics

Starter code: #User function Template for python3



class Solution:

    def smallestpositive(self, array, n): 

        # Your code goes here  

Solutions:
class Solution:

	def smallestpositive(self, arr, n):
		mis = 1
		arr.sort()
		for i in range(n):
			if mis < arr[i]:
				return mis
			else:
				mis += arr[i]
		return mis


class Solution:

	def smallestpositive(self, array, n):
		array.sort()
		res = 1
		for a in array:
			if a <= res:
				res += a
			else:
				break
		return res


class Solution:

	def smallestpositive(self, array, n):
		array.sort()
		result = 1
		for val in array:
			if val > result:
				return result
			else:
				result = result + val
		return result


class Solution:

	def smallestpositive(self, array, n):
		array.sort()
		curr_sum = 0
		for i in range(n):
			if curr_sum < array[i] - 1:
				return curr_sum + 1
			else:
				curr_sum += array[i]
		return curr_sum + 1


class Solution:

	def smallestpositive(self, array, n):
		max_constructible_sum = 0
		for c in sorted(array):
			if c > max_constructible_sum + 1:
				return max_constructible_sum + 1
			max_constructible_sum += c
		return max_constructible_sum + 1


class Solution:

	def smallestpositive(self, array, n):
		array.sort()
		smallest = 1
		for i in range(n):
			if array[i] <= smallest:
				smallest += array[i]
			else:
				break
		return smallest


class Solution:

	def smallestpositive(self, array, n):
		array.sort()
		j = 1
		sum = 1
		for i in range(n):
			if sum < array[i]:
				return sum
			else:
				sum += array[i]
		return sum


from collections import defaultdict

class Solution:

	def smallestpositive(self, a, n):
		a.sort()
		s = 1
		for i in range(n):
			if a[i] > s:
				return s
			s += a[i]
		return s


class Solution:

	def smallestpositive(self, array, n):
		total = 1
		array.sort()
		for i in array:
			if i <= total:
				total += i
		return total


class Solution:

	def smallestpositive(self, array, n):
		array.sort()
		out = 1
		for i in range(n):
			if array[i] <= out:
				out = out + array[i]
		return out


class Solution:

	def smallestpositive(self, array, n):
		array.sort()
		smallest_int = 1
		for i in range(n):
			if array[i] <= smallest_int:
				smallest_int += array[i]
			else:
				return smallest_int
		return smallest_int


class Solution:

	def smallestpositive(self, array, n):
		min = 1
		array.sort()
		for i in array:
			if min < i:
				return min
			else:
				min += i
		return min


class Solution:

	def smallestpositive(self, a, n):
		a.sort()
		s = 0
		for i in range(n):
			if a[i] > s + 1:
				return s + 1
			s += a[i]
		return s + 1


from itertools import combinations

class Solution:

	def smallestpositive(self, array, n):
		array.sort()
		mis = 1
		for i in range(n):
			if mis < array[i]:
				return mis
			else:
				mis = mis + array[i]
		return mis

	def smallestpositive1(self, array, n):
		result = 0
		possibles = set()
		for i in range(1, n + 1):
			possible_numbers = combinations(array, i)
			for item in possible_numbers:
				possibles.add(sum(item))
		x = min(min(array), 1)
		while x in possibles:
			x = x + 1
		return x


from itertools import combinations

class Solution:

	def smallestpositive(self, array, n):
		result = 1
		array.sort()
		for i in range(n):
			if result < array[i]:
				return result
			else:
				result += array[i]
		return result


class Solution:

	def smallestpositive(self, array, n):
		array.sort()
		res = 1
		i = 0
		while i < n and array[i] <= res:
			res = res + array[i]
			i += 1
		return res


class Solution:

	def smallestpositive(self, array, n):
		array.sort()
		s = 0
		sa = 1
		for i in range(n):
			s = s + array[i]
			if sa >= array[i] or sa >= s:
				sa += array[i]
			else:
				return sa
		return s + 1


class Solution:

	def smallestpositive(self, arr, n):
		smallest = 1
		arr.sort()
		for i in range(len(arr)):
			if arr[i] <= smallest:
				smallest += arr[i]
			else:
				return smallest
		return smallest


class Solution:

	def smallestpositive(self, array, n):
		res_arr = [0] * n
		array.sort()
		sum = array[0]
		if array[0] != 1:
			return 1
		for idx in range(1, n):
			if array[idx] - sum > 1:
				return sum + 1
			sum += array[idx]
		return sum + 1


class Solution:

	def smallestpositive(self, array, n):
		array.sort()
		sum = 0
		temp = 1
		for i in range(n):
			if array[i] <= temp:
				sum += array[i]
				temp = sum + 1
		return temp


class Solution:

	def smallestpositive(self, array, n):
		array.sort()
		res = 0
		target = 1
		for i in range(n):
			if array[i] <= target:
				res += array[i]
				target = res + 1
		return target


class Solution:

	def smallestpositive(self, a, n):
		a.sort()
		res = 1
		for i in range(n):
			if res < a[i]:
				return res
			else:
				res = res + a[i]
		return res


class Solution:

	def smallestpositive(self, arr, n):
		arr.sort()
		result = 1
		for i in range(n):
			if arr[i] > result:
				return result
			result += arr[i]
		return result


class Solution:

	def smallestpositive(self, arr, n):
		arr.sort()
		if arr[0] != 1:
			return 1
		cur = 1
		for i in range(n):
			if arr[i] <= cur:
				cur += arr[i]
			else:
				break
		return cur


class Solution:

	def smallestpositive(self, array, n):
		re = 1
		array.sort()
		for h in array:
			if h <= re:
				re += h
			else:
				break
		return re


class Solution:

	def smallestpositive(self, a, n):
		ans = 1
		a.sort()
		for i in range(n):
			if ans < a[i]:
				return ans
			ans += a[i]
		return ans


class Solution:

	def smallestpositive(self, array, n):
		maxi = 1
		array.sort()
		if array[0] != 1 or n == 0:
			return 1
		for i in range(1, n):
			if array[i] > maxi + 1:
				return maxi + 1
			maxi += array[i]
		return maxi + 1


class Solution:

	def smallestpositive(self, array, n):
		array.sort()
		max_val = 0
		sum_val = [0] * (n + 1)
		for i in range(1, n + 1):
			sum_val[i] = sum_val[i - 1] + array[i - 1]
		for i in range(n):
			if array[i] > max_val + 1:
				return max_val + 1
			max_val = max(max_val, sum_val[i + 1])
		return max_val + 1


class Solution:

	def smallestpositive(self, array, n):
		arr = sorted(array)
		max_sum = 0
		for i in arr:
			if i <= max_sum + 1:
				max_sum += i
			else:
				return max_sum + 1
		return max_sum + 1