Given a sorted array of N positive integers, find the smallest positive integer S such that S cannot be represented as sum of elements of any subset of the given array set.
Example 1:
Input:
N = 3
Arr[] = {1, 2, 3}
Output: 7
Explanation: 7 is the smallest positive number 
for which any subset is not present with sum 7.
Example 2:
Input:
N = 6
Arr[] = {3, 6, 9, 10, 20, 28}
Output: 1
Explanation: 1 is the smallest positive number
for which any subset is not present with sum 1.
Your Task:
You don't need to read input or print anything. Your task is to complete the function findSmallest() which takes the array of integers arr and its size n as input parameters and returns an integer denoting the answer.
 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints
1 <= N <= 10^{6}
0 <= Arr[i] <= 10^{15}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Starter code: #User function Template for python3



class Solution:

    def findSmallest(self, arr, n):

        # code here

Solutions:
class Solution:

	def findSmallest(self, arr, n):
		ans = 1
		for a in arr:
			if a > ans:
				return ans
			ans += a
		return ans


class Solution:

	def findSmallest(self, arr, n):
		res = 1
		for i in range(n):
			if arr[i] <= res:
				res += arr[i]
			else:
				break
		return res


class Solution:

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


class Solution:

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


class Solution:

	def findSmallest(self, arr, n):
		target = 0
		for i in range(n):
			if arr[i] > target + 1:
				return target + 1
			target += arr[i]
		return target + 1


class Solution:

	def findSmallest(self, arr, n):
		t = 1
		for i in range(n):
			if arr[i] <= t:
				t += arr[i]
			else:
				return t
		return t


class Solution:

	def findSmallest(self, arr, n):
		mp = arr[0]
		cr = 1
		for i in range(0, n):
			if arr[i] > cr:
				break
			else:
				cr += arr[i]
		return cr


class Solution:

	def findSmallest(self, arr, n):
		ans = 1
		arr.sort()
		for i in range(0, n):
			if ans == arr[i] or arr[i] < ans:
				ans += arr[i]
		return ans


class Solution:

	def findSmallest(self, arr, n):
		prev = 0
		ans = 0
		for i in range(n):
			prev += arr[i]
			if prev - ans <= ans + 1:
				ans += prev - ans
			else:
				return ans + 1
		return ans + 1


class Solution:

	def findSmallest(self, arr, n):
		count = 0
		for i in arr:
			if i > count + 1:
				return count + 1
			else:
				count += i
		return count + 1


class Solution:

	def findSmallest(self, arr, n):
		s = 1
		for i in range(n):
			if arr[i] <= s:
				s += arr[i]
		return s


class Solution:

	def findSmallest(self, arr, n):
		c = 1
		for i in range(n):
			if arr[i] <= c:
				c += arr[i]
		return c
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		ans = ob.findSmallest(arr, n)
		print(ans)
		tc -= 1


class Solution:

	def findSmallest(self, arr, n):
		i = 0
		res = 1
		while i < n and arr[i] <= res:
			res += arr[i]
			i += 1
		return res


class Solution:

	def findSmallest(self, arr, n):
		num = 1
		for i in range(n):
			if arr[i] > num:
				return num
			else:
				num += arr[i]
		return sum(arr) + 1


class Solution:

	def findSmallest(self, arr, n):
		curr = 0
		if len(arr) == 0 or arr[0] > 1:
			return 1
		for n in arr:
			if n > curr + 1:
				return curr + 1
			else:
				curr += n
		return curr + 1


class Solution:

	def findSmallest(self, arr, n):
		curr = 1
		for x in arr:
			if curr < x:
				return curr
			else:
				curr = x + curr
		return curr


class Solution:

	def findSmallest(self, arr, n):
		res = 1
		for num in arr:
			if num > res:
				return res
			res += num
		return res


class Solution:

	def findSmallest(self, input_list, n):
		min_num = 1
		for num in input_list:
			if num > min_num:
				return min_num
			min_num += num
		return min_num


class Solution:

	def findSmallest(self, ordered_array, n):
		elem_sum_plus_1 = 1
		for i in range(len(ordered_array)):
			if ordered_array[i] > elem_sum_plus_1:
				return elem_sum_plus_1
			elem_sum_plus_1 += ordered_array[i]
		return elem_sum_plus_1


class Solution:

	def findSmallest(self, array, n):
		result = 1
		for i in range(0, n):
			if array[i] <= result:
				result += arr[i]
			else:
				break
		return result


class Solution:

	def findSmallest(self, arr, n):
		ret = 1
		arr_iter = iter(arr)
		current_num = next(arr_iter)
		while ret >= current_num:
			ret += current_num
			try:
				current_num = next(arr_iter)
			except StopIteration:
				break
		return ret


class Solution:

	def findSmallest(self, arr, n):
		smallestPosVal = arr[0] + 1
		if smallestPosVal > 2:
			return 1
		for i in range(1, n):
			if arr[i] > smallestPosVal:
				return smallestPosVal
			smallestPosVal += arr[i]
		return smallestPosVal


class Solution:

	def findSmallest(self, arr, n):
		m = 0
		for a in arr:
			if a > m + 1:
				return m + 1
			else:
				m += a
		return m + 1


class Solution:

	def findSmallest(self, arr, n):
		imp_sum = 1
		for i in arr:
			if i <= imp_sum:
				imp_sum += i
			else:
				break
		return imp_sum


class Solution:

	def findSmallest(self, arr, n):
		ans = 1
		s1 = 0
		for num in arr:
			if num > ans:
				return ans
			ans += num
		return ans