N children are made to stand in a queue. Each of them is given a number A[i]. The teacher writes a number S on a page and passes it to the first child. Each child must add all the numbers they see on the page along with their own number, write the sum on the paper and pass it to the next person. 
In the end, the teacher must determine if X can be formed by adding some of the numbers from the series of numbers written on the paper.
Example 1:
Input: 
S = 1, N = 4, X = 7
A = {1, 2, 4, 2}
Output: yes
Explaination: The final sequence of 
numbers on the paper is 1, 2, 5, 12, 22. 
Using 2 and 5 we can form 7. 
Example 2:
Input: 
S = 100, N = 2, X = 500
A = {51, 88}
Output: no
Explaination: The final sequence of 
numbers on the paper is 100, 151, 339. 
Using these numbers we cannot form 500.
Your Task:
You do not need to read input or print anything. Your task is to complete the function isPossible() which takes S, N, X and array A as input parameters and returns 1 if there is a subset which adds to this sum. Otherwise returns 0.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
 
Constraints
1 ≤ N ≤ 10^{5}
1 ≤ S, A_{i} , X ≤ 10^{18}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Greedy algorithms

Starter code: #User function Template for python3



class Solution:

    def isPossible(self, S, N, X, A):

        # code here

Solutions:
class Solution:

	def isPossible(self, S, N, X, A):
		newArray = [S]
		sumArr = newArray[0]
		temp = 0
		for i in range(1, N + 1):
			newArray.append(A[i - 1] + sumArr)
			if newArray[i] > X:
				temp = i
				break
			sumArr += newArray[i]
		for i in range(temp - 1, -1, -1):
			if X < newArray[i]:
				continue
			else:
				X -= newArray[i]
			if X == 0:
				return 1
		return 0


class Solution:

	def isPossible(self, S, N, X, A):
		a = [S]
		total = S
		for i in range(N):
			a.append(total + A[i])
			total += a[-1]
		j = N
		while j >= 0 and X > 0:
			if X >= a[j]:
				X -= a[j]
			j -= 1
		return 1 if X == 0 else 0


class Solution:

	def isPossible(self, S, N, X, A):
		s = [0] * (N + 1)
		s[0] = S
		s[1] = A[0] + S
		j = 0
		for i in range(2, N + 1):
			s[i] = s[i - 1] - A[j] + s[i - 1] + A[i - 1]
			j += 1
		for i in range(len(s) - 1, -1, -1):
			if s[i] > X:
				continue
			else:
				X -= s[i]
				if X == 0:
					return 1
		return 0


class Solution:

	def isPossible(self, S, N, X, A):
		summa = S
		stack = [summa]
		for item in A:
			stack.append(summa + item)
			summa = summa * 2 + item
		while stack and X:
			if stack[-1] <= X:
				X -= stack[-1]
			stack.pop()
		return X == 0


class Solution:

	def isPossible(self, S, N, X, A):
		t = [S]
		k = S
		for i in A:
			S = k + i
			t.append(S)
			k += S
		t.sort()
		for i in range(len(t) - 1, -1, -1):
			if X >= t[i]:
				X -= t[i]
			if X == 0:
				return 1
		return 0


class Solution:

	def isPossible(self, S, N, X, A):
		p = [0] * (N + 1)
		p[0] = S
		s = S
		for i in range(N):
			p[i + 1] = s + A[i]
			if p[i + 1] >= X:
				break
			s += p[i + 1]
		i = len(p) - 1
		while i >= 0 and X > 0:
			if X >= p[i]:
				X -= p[i]
			i -= 1
		if X == 0:
			return 1
		return 0
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(S, N, X) = [int(y) for y in input().split()]
		A = input().split()
		for i in range(N):
			A[i] = int(A[i])
		ob = Solution()
		if ob.isPossible(S, N, X, A) == 1:
			print('yes')
		else:
			print('no')


class Solution:

	def isPossible(self, S, N, X, A):
		p = [S]
		for i in range(len(A)):
			p.append(A[i] + S)
			r = S + A[i]
			S += r
		i = len(p) - 1
		while i >= 0:
			if X - p[i] >= 0:
				X -= p[i]
			i -= 1
		if X == 0:
			return True
		return False
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(S, N, X) = [int(y) for y in input().split()]
		A = input().split()
		for i in range(N):
			A[i] = int(A[i])
		ob = Solution()
		if ob.isPossible(S, N, X, A) == 1:
			print('yes')
		else:
			print('no')


class Solution:

	def isPossible(self, S, N, X, A):
		l = [S]
		pre = S
		for i in range(N):
			pre += A[i]
			l.append(pre)
			pre += l[i + 1]
		i = N
		while i >= 0 and X > 0:
			if X >= l[i]:
				X -= l[i]
			i -= 1
		if X == 0:
			return True
		return False


class Solution:

	def isPossible(self, S, N, X, A):
		a = [S]
		k = S
		for i in range(N):
			a.append(k + A[i])
			k = a[-1] + k
		for i in range(len(a) - 1, -1, -1):
			if a[i] > X:
				continue
			else:
				X -= a[i]
				if X == 0:
					return True
		return False


class Solution:

	def isPossible(self, S, N, X, A):
		series = []
		series.append(S)
		tot = S
		pre = S
		for i in range(0, N):
			series.append(tot + A[i])
			tot = tot + series[-1]
		series.sort()
		for i in range(len(series) - 1, -1, -1):
			if series[i] > X:
				continue
			else:
				X = X - series[i]
				if X == 0:
					return True
		return False


class Solution:

	def isPossible(self, S, N, X, A):
		l = []
		l.append(S)
		s1 = S
		s2 = 0
		for i in A:
			s2 = s1 + i
			if s2 > X:
				break
			l.append(s2)
			s1 = s2 + s1
		i = len(l) - 1
		while i >= 0 and X > 0:
			if X >= l[i]:
				X -= l[i]
			i -= 1
		if X == 0:
			return 1
		return 0
		return 1


class Solution:

	def isPossible(self, S, N, X, A):
		Papers = [0 for _ in range(N + 1)]
		Papers[0] = S
		Sum = S
		for i in range(N):
			Papers[i + 1] = Sum + A[i]
			if Papers[i + 1] > X:
				break
			Sum += Papers[i + 1]
		j = len(Papers) - 1
		while j >= 0 and X > 0:
			if X >= Papers[j]:
				X -= Papers[j]
			j -= 1
		if X == 0:
			return 1
		return 0


class Solution:

	def isPossible(self, S, N, X, A):
		l = []
		l.append(S)
		prev = S
		for i in range(len(A)):
			curr = A[i] + prev
			l.append(curr)
			prev += curr
			if prev > X:
				break
		for i in range(len(l) - 1, -1, -1):
			if l[i] <= X:
				X -= l[i]
			if X == 0:
				return 1
		return 0


class Solution:

	def isPossible(self, S, N, X, A):
		s = S
		c = 0
		for i in range(N):
			A[i] += s
			s += A[i]
			c = i
			if s > X:
				break
		if s == X:
			return True
		while X >= 0 and c >= 0:
			if X >= A[c]:
				X -= A[c]
			if X == 0 or X - S == 0:
				return True
			c -= 1
		return False


class Solution:

	def isPossible(self, S, N, X, A):
		number_paper = []
		number_paper.append(S)
		sum_paper = S
		for i in A:
			number_paper.append(sum_paper + i)
			sum_paper += sum_paper + i
			if sum_paper > X:
				break
		n = len(number_paper) - 1
		while n >= 0:
			if X >= number_paper[n]:
				X -= number_paper[n]
			n -= 1
			if X == 0:
				return True
		return False


class Solution:

	def isPossible(self, S, N, X, A):
		curr_sum = S
		num = []
		num.append(curr_sum)
		for i in A:
			sum_i = curr_sum + i
			if sum_i <= X:
				num.append(sum_i)
				curr_sum += sum_i
			else:
				break
		for i in reversed(num):
			if X >= i:
				X -= i
			if X == 0:
				return 1
		return 0


class Solution:

	def isPossible(self, s, n, x, a):
		list = [s]
		list.append(s + a[0])
		sum = s + a[0]
		b = 0
		for i in range(1, n):
			list.append(s + sum + a[i])
			if list[i] > x:
				b = i
				break
			sum = sum + list[i + 1]
		for i in range(b - 1, -1, -1):
			if list[i] == x:
				return 1
			if list[i] > x:
				continue
			else:
				x = x - list[i]
			if x == 0:
				return 1
		return 0


class Solution:

	def print(self, *args):
		pass

	def isPossible(self, S, N, X, A):
		bResult = False
		iSum = S
		listB = [iSum]
		for iIndex in range(N):
			iSumPre = iSum
			iSum += A[iIndex]
			listB.append(iSum)
			iSum += iSumPre
		if X in listB:
			self.print('found in listB')
			return True
		self.print('listB', listB)
		iLeft = 0
		iRight = len(listB) - 1
		while iLeft < iRight:
			iSum = listB[iLeft] + listB[iRight]
			self.print('loop', listB[iLeft], listB[iRight], iSum)
			if iSum == X:
				self.print('found as sum of two', listB[iLeft], listB[iRight])
				bResult = True
				return bResult
				break
			elif iSum < X:
				iLeft += 1
			else:
				iRight -= 1
		iMaxValue = -1
		iMaxIndex = -1
		iLastIndexUsed = -1
		iDiff = X
		self.print('start iDiff', iDiff)
		while iDiff > 0:
			self.print('loop iDiff', iDiff)
			for iIndex in range(len(listB)):
				if listB[iIndex] > iDiff:
					break
				elif iIndex != iLastIndexUsed:
					iMaxIndex = iIndex
					iMaxValue = listB[iIndex]
					iLastIndexUsed = iIndex
				else:
					iMaxValue = -1
			if iMaxValue >= 0:
				iDiff = iDiff - iMaxValue
			else:
				break
			if iDiff == 0:
				return True
			self.print('iMaxIndex', iMaxIndex, 'iMaxValue', iMaxValue, 'iDiff', iDiff)
		return bResult
		return bResult
		dictC = dict()
		for iFirst in range(0):
			for iSecond in range(iFirst + 1, len(listB)):
				iSum = listB[iFirst] + listB[iSecond]
				self.print('iSum', iSum, 'at', iFirst, iSecond)
				if iSum < X:
					listSource = [listB[iFirst], listB[iSecond]]
					if iSum in dictC:
						dictC[iSum].append(list.Source)
					else:
						dictC[iSum] = listSource
		self.print('dictC ', dictC)
		listC = list(dictC.keys())
		listC.sort()
		self.print('listC', listC)
		return bResult


class Solution:

	def isPossible(self, S, N, X, A):
		if S == X:
			return 1
		_list = [S]
		prev = S
		for i in A:
			cur = prev + i
			_list.append(cur)
			prev += cur
			if prev > X:
				break
		_list.sort(reverse=True)
		for i in _list:
			if i <= X:
				X -= i
			if X == 0:
				return 1
		return 0


class Solution:

	def isPossible(self, s, n, x, a):
		l1 = [s]
		for i in range(n):
			y = s + a[i]
			l1.append(y)
			s += l1[-1]
		for i in range(len(l1) - 1, -1, -1):
			if l1[i] > x:
				continue
			else:
				x = x - l1[i]
				if x == 0:
					return True
		return False


class Solution:

	def isPossible(self, S, N, X, A):
		sums = [S]
		prev = S
		for num in A:
			cur = prev + num
			sums.append(cur)
			prev += cur
		for i in range(len(sums) - 1, -1, -1):
			if X >= sums[i]:
				X -= sums[i]
			if X == 0:
				return True
		return False


class Solution:

	def isPossible(self, S, N, X, A):
		(res, temp, s, x) = ([S], S, S, N)
		for i in range(N):
			s += A[i]
			if s > X:
				x = i - 1
			res.append(s)
			temp += res[-1]
			s = temp
		while x >= 0:
			if X == 0:
				break
			if res[x] <= X and X > 0:
				X -= res[x]
			x -= 1
		return 1 if X == 0 else 0


class Solution:

	def isPossible(self, S, N, X, A):
		a = []
		b = []
		a.append(0)
		b.append(S)
		for i in range(1, N + 1):
			a.append(a[i - 1] + b[i - 1])
			b.append(a[i] + A[i - 1])
			if a[i] == X or b[i] == X:
				return 1
			if b[i] > X:
				break
		while i >= 0:
			i -= 1
			if X == b[i] or X == a[i]:
				return 1
			if X > b[i]:
				X -= b[i]
				if X > a[i]:
					return 0


class Solution:

	def isPossible(self, S, N, X, A):
		numbers = [S]
		sumar = numbers[0]
		temp = 0
		for i in range(1, N + 1):
			numbers.append(A[i - 1] + sumar)
			if numbers[i] > X:
				temp = i
				break
			sumar += numbers[i]
		for i in range(temp - 1, -1, -1):
			if X < numbers[i]:
				continue
			else:
				X -= numbers[i]
			if X == 0:
				return 1
		return 0


class Solution:

	def isPossible(self, S, N, X, A):
		start = S
		temp = [0] * (N + 1)
		temp[0] = S
		for i in range(0, N):
			curr = start + A[i]
			temp[i + 1] = curr
			start += curr
		l = 0
		while l <= N and X >= temp[l]:
			if X == temp[l]:
				return True
			l += 1
		if l == 0:
			return False
		t = l - 1
		while t >= 0:
			if X == 0:
				return True
			if temp[t] <= X:
				X -= temp[t]
				if X == 0:
					return True
			t -= 1
		return False


from functools import reduce

class Solution:

	def isPossible(self, S, N, X, A):
		output = [S]
		for i in range(N):
			nxtValue = sum(output) + A[i]
			if nxtValue == X:
				return 1
			elif nxtValue > X:
				break
			else:
				output.append(nxtValue)
		for o in output[::-1]:
			if X >= o:
				X -= o
			if X == 0 or X - S == 0:
				return 1
		return 0


class Solution:

	def isPossible(self, S, N, X, A):
		P = [S]
		prev = S
		for i in range(N):
			currsum = A[i] + prev
			P.append(currsum)
			prev = prev + currsum
			if prev > X:
				break
		for p in range(len(P) - 1, -1, -1):
			if P[p] <= X:
				X = X - P[p]
			if X == 0:
				return 1
		return 0


class Solution:

	def isPossible(self, S, N, X, A):
		B = [S]
		sumVal = S
		temp = 0
		for i in range(1, N + 1):
			B.append(A[i - 1] + sumVal)
			if B[i] > X:
				temp = i
				break
			sumVal += B[i]
		for i in range(temp - 1, -1, -1):
			if X < B[i]:
				continue
			else:
				X -= B[i]
			if X == 0:
				return 1
		return 0


class Solution:

	def isPossible(self, S, N, X, A):
		page = [S]
		total = 0
		for num in A:
			total += page[-1]
			page.append(total + num)
		for num in page[::-1]:
			if num == X:
				return 1
			elif num < X:
				X -= num
		return 0


class Solution:

	def isPossible(self, S, N, X, A):
		summ = S
		prev_sum = 0
		seq_ary = [S]
		for i in A:
			prev_sum += summ
			summ = i + prev_sum
			if summ > X:
				break
			seq_ary.append(summ)
		for i in range(len(seq_ary) - 1, -1, -1):
			if X >= seq_ary[i]:
				X -= seq_ary[i]
		if X == 0:
			return 1
		else:
			return 0


class Solution:

	def isPossible(self, S, N, X, A):
		temp = []
		temp.append(S)
		sum1 = S
		xpoint = 0
		for i in range(N):
			temp.append(A[i] + sum1)
			sum1 = sum(temp)
			if sum1 == X:
				return 1
			elif temp[-1] > X:
				break
		n = len(temp)
		for i in range(n - 1, -1, -1):
			if temp[i] <= X:
				X = X - temp[i]
		if X == 0:
			return 1
		return 0


class Solution:

	def isPossible(self, S, N, X, A):
		l = [S]
		sum_ = S
		for a in A:
			t = sum_
			sum_ += a
			l.append(sum_)
			sum_ += t
		for i in range(len(l) - 1, -1, -1):
			if l[i] <= X:
				X -= l[i]
		return X == 0


class Solution:

	def isPossible(self, S, N, X, A):
		v = []
		v.append(S)
		cur = S
		for i in range(N):
			temp = cur + A[i]
			v.append(temp)
			if temp >= X:
				break
			cur = cur + temp
		i = len(v) - 1
		while i >= 0 and X > 0:
			if X >= v[i]:
				X = X - v[i]
			i = i - 1
		if X == 0:
			return 1
		return 0


class Solution:

	def isPossible(self, S, N, X, A):
		arr = [0] * (N + 1)
		x = S
		arr[0] = S
		for i in range(1, N + 1):
			arr[i] = A[i - 1] + x
			x += arr[i]
		j = N
		while X and j >= 0:
			if arr[j] <= X:
				X -= arr[j]
			j -= 1
		return X == 0


class Solution:

	def isPossible(self, S, N, X, A):
		start = S
		i = 0
		for i in range(0, N):
			A[i] += start
			start += A[i]
			if start > X:
				break
		if start == X:
			return 1
		while X >= 0 and i >= 0:
			if X >= A[i]:
				X -= A[i]
			if X == 0 or X - S == 0:
				return 1
			i -= 1
		return 0


from bisect import bisect_left

class Solution:

	def isPossible(self, S, N, X, A):
		sum_arr = [S]
		cur = S
		for i in range(N):
			temp = A[i] + cur
			sum_arr.append(temp)
			if temp >= X:
				break
			cur += temp
		i = len(sum_arr) - 1
		while i >= 0 and X > 0:
			if X >= sum_arr[i]:
				X -= sum_arr[i]
			i -= 1
		return True if X == 0 else False


class Solution:

	def isPossible(self, S, N, X, A):
		sum_val = S
		values = [S]
		for symbol in A:
			if sum_val + symbol > X:
				break
			values.append(sum_val + symbol)
			sum_val += sum_val + symbol
		values = values[::-1]

		def Search(new_val, values):
			if new_val == 0:
				return 1
			if len(values) == 0:
				return 0
			if new_val > 0:
				for (j, value) in enumerate(values):
					bla = Search(new_val - value, values[j + 1:])
					if bla == 1:
						return 1
			return 0
		if Search(X, values) == 1:
			return 1
		return 0


class Solution:

	def isPossible(self, S, N, X, A):
		dummy = [S]
		dummy_sum = S
		temp = 0
		for i in range(1, N + 1):
			dummy.append(A[i - 1] + dummy_sum)
			if dummy[i] > X:
				temp = i
				break
			else:
				dummy_sum += dummy[i]
		for i in range(temp - 1, -1, -1):
			if X == 0:
				return 1
			if X >= dummy[i]:
				X -= dummy[i]
				if X == 0:
					return 1
		return 0


class Solution:

	def isPossible(self, S, N, X, A):
		l = [S]
		l.sort()
		su = sum(l)
		for i in range(0, len(A)):
			k = su + A[i]
			su = su + k
			l.append(k)
		for i in range(len(l) - 1, -1, -1):
			if l[i] > X:
				continue
			else:
				X -= l[i]
				if X == 0:
					return True
		return False


class Solution:

	def isPossible(self, S, n, x, arr):
		(page, sop) = ([], [])
		page.append(S)
		sop.append(S)
		i = 0
		while i < n and page[-1] <= X:
			page.append(arr[i] + sop[-1])
			sop.append(sop[-1] + page[-1])
			i += 1
		while i >= 0:
			if x >= page[i]:
				x -= page[i]
			if x == 0:
				return 1
			i -= 1
		return 0


class Solution:

	def isPossible(self, S, N, X, A):
		total = S
		lst = []
		lst.append(S)
		for i in range(N):
			val = total + A[i]
			lst.append(val)
			total += val
			if total == X:
				return True
			if total > X:
				break
		for i in range(len(lst) - 1, -1, -1):
			if X >= lst[i]:
				X -= lst[i]
			if X == 0 or X - S == 0:
				return True
		return False


import numpy as np

class Solution:

	def isPossible(self, S, N, X, A):
		v = S
		for i in range(N):
			A[i] += v
			v += A[i]
			if v > X:
				break
		while X >= 0 and i >= 0:
			if X >= A[i]:
				X -= A[i]
			if X == 0 or X == S:
				return True
			i -= 1
		return False


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def isPossible(self, S, N, X, A):
		dp = [0] * (N + 1)
		dp[0] = S
		total = S
		for (i, num) in enumerate(A):
			dp[i + 1] = total + num
			total += dp[i + 1]
			if dp[i + 1] > X:
				dp[i + 1] = 0
				break
		j = i + 1
		while j >= 0:
			if X >= dp[j]:
				X -= dp[j]
			if X == 0:
				return True
			j -= 1
		return False


class Solution:

	def isPossible(self, s, n, x, a):
		newArray = [s]
		sumArr = newArray[0]
		temp = 0
		for i in range(1, N + 1):
			newArray.append(a[i - 1] + sumArr)
			if newArray[i] > x:
				temp = i
				break
			sumArr += newArray[i]
		for i in range(temp - 1, -1, -1):
			if x < newArray[i]:
				continue
			else:
				x -= newArray[i]
			if x == 0:
				return 1
		return 0


class Solution:

	def isPossible(self, s, N, x, A):
		res = [s]
		res.append(res[-1] + A[0])
		for i in range(1, N):
			res.append(2 * res[-1] - A[i - 1] + A[i])
			if res[-1] > x:
				break
		for i in range(len(res) - 1, -1, -1):
			if x >= res[i]:
				x -= res[i]
				if x == 0:
					return 1
		return 0


class Solution:

	def isPossible(self, S, N, X, A):
		arr = [S]
		sumarr = S
		temp = 0
		for i in range(N):
			arr.append(A[i] + sumarr)
			if arr[i + 1] > X:
				temp = i + 1
				break
			sumarr += arr[i + 1]
		for i in range(temp - 1, -1, -1):
			if X >= arr[i]:
				X -= arr[i]
			if X == 0:
				return 1
		return 0


class Solution:

	def isPossible(self, S, N, X, A):
		ans = [S]
		anssum = S
		for i in range(N):
			cur = anssum + A[i]
			if cur > X:
				break
			ans.append(cur)
			anssum += cur
		n = len(ans)
		i = n - 1
		while X > 0 and i > -1:
			if ans[i] <= X:
				X -= ans[i]
			i -= 1
		return X == 0


class Solution:

	def isPossible(self, S, N, X, A):
		ini = [S]
		prev = S
		for i in A:
			total = prev + i
			ini.append(total)
			prev = prev + total
		flag = True
		for i in range(len(ini) - 1, -1, -1):
			if ini[i] <= X:
				X -= ini[i]
				if X == 0:
					return True
				elif X < 0:
					break
		if flag == False:
			return flag
		if X == 0:
			return True
		else:
			return False


class Solution:

	def isPossible(self, s, n, x, a):
		ans = [s]
		for i in range(n):
			ans.append(a[i])
		index = n
		for i in range(1, n + 1):
			ans[i] += s
			s += ans[i]
			if s > x:
				index = i
				break
		i = index
		while i >= 0:
			if ans[i] <= x:
				x -= ans[i]
			if x == 0:
				return 1
			i -= 1
		return x == 0