Given a string, the task is to find whether it contains an additive sequence or not. A string contains an additive sequence if its digits can make a sequence of numbers in which every number is addition of previous two numbers. You are required to complete the function which returns true if the string is a valid sequence else returns false.
Input:
The first line of input contains an integer T denoting the no of test cases . Then T test cases follow . Each test case contains a string s .
Output:
For each test case in a new line output will be 1 if it contains an additive sequence and 0 if it doesn't contains an additive sequence.
Constraints:
1<=T<=100
1<=length of string<=200
Example:
Input
3
1235813
1711
199100199
Output
1
0
1
Explanation:
1. In first test case series will be (1 2 3 5 8 13 ) as 1+2=3, 2 + 3 = 5, 3 + 5 = 8, 5 + 8 = 13 .
2. In the second test case there is no such series possible.
3. In the third test case there is the series will be 1 99 100 199 .
Note:The Input/Ouput format and Example given are used for system's internal purpose, and should be used by a user for Expected Output only. As it is a function problem, hence a user should not read any input from stdin/console. The task is to complete the function specified, and not to write the full code.

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Data structures

Complete search

Starter code: #User function Template for python3



def isAdditiveSequence(num):

    #code here

Solutions:
def solve(a, b, s, k, n, start=0):
	if k == n and start > 0:
		return 1
	for i in range(1, n):
		if k + i > n:
			break
		c = int(s[k:k + i])
		if c == a + b:
			return solve(b, c, s, k + i, n, start + 1)
		elif c > a + b:
			return 0
	return 0

def isAdditiveSequence(num):
	n = len(num)
	for i in range(1, n):
		for j in range(1, n):
			a = int(num[0:i])
			b = int(num[i:i + j])
			if solve(a, b, num, i + j, n):
				return 1
	return 0


def checkIsAdditive(nums):
	if len(nums) < 3:
		return True
	for i in range(2, len(nums)):
		if int(nums[i - 2]) + int(nums[i - 1]) != int(nums[i]):
			return False
	return True

def isAdditiveSequence(num):
	additiveSubsequenceFound = False

	def recur(str, sub):
		nonlocal additiveSubsequenceFound
		if len(str) == 0:
			if len(sub.split(' ')) >= 3 and checkIsAdditive(sub.split(' ')):
				additiveSubsequenceFound = True
			return
		if additiveSubsequenceFound:
			return
		if len(sub) != 0 and checkIsAdditive(sub.split(' ')):
			recur(str[1:], sub + ' ' + str[0])
		recur(str[1:], sub + str[0])
	recur(str(num), '')
	return 1 if additiveSubsequenceFound else 0


n = 0

def find(s, a, b, c, d):
	ans = 0
	if a == n:
		return 1 if d >= 3 else 0
	for i in range(a, n):
		ans = ans * 10 + int(s[i])
		if ans == 0:
			if b == -1 or c == -1:
				if b == -1:
					return find(s, a + 1, ans, c, d + 1)
				else:
					return find(s, a + 1, b, ans, d + 1)
			elif b + c == ans:
				return find(s, a + 1, c, ans, d + 1)
			else:
				return 0
		elif b == -1 or c == -1:
			if b == -1:
				if find(s, i + 1, ans, c, d + 1):
					return 1
			elif find(s, i + 1, b, ans, d + 1):
				return 1
		elif b + c == ans:
			return find(s, i + 1, c, ans, d + 1)
		elif ans > b + c:
			return 0
	return 0

def isAdditiveSequence(num):
	global n
	n = len(s)
	return find(num, 0, -1, -1, 0)


n = 0

def dfs(s, a, l):
	ans = 0
	if a == n:
		return 1 if len(l) >= 3 else 0
	for i in range(a, n):
		ans = ans * 10 + int(s[i])
		if ans == 0:
			if len(l) < 2:
				l.append(ans)
				b = dfs(s, a + 1, l)
				l.pop()
				return b
			elif ans == l[-1] + l[-2]:
				l.append(ans)
				b = dfs(s, a + 1, l)
				l.pop()
				return b
			else:
				return 0
		elif len(l) < 2:
			l.append(ans)
			if dfs(s, i + 1, l) == 1:
				return 1
			l.pop()
		elif ans == l[-1] + l[-2]:
			l.append(ans)
			if dfs(s, i + 1, l) == 1:
				return 1
			l.pop()
		elif ans > l[-1] + l[-2]:
			return 0
	return 0

def isAdditiveSequence(s):
	global n
	n = len(s)
	return dfs(s, 0, [])


def rec(s, beg, l1, l2):
	s1 = s[beg:beg + l1]
	s2 = s[beg + l1:beg + l1 + l2]
	s3 = str(int(s1) + int(s2))
	l3 = len(s3)
	if beg + l1 + l2 + l3 > len(s):
		return False
	elif s3 == s[beg + l1 + l2:beg + l1 + l2 + l3]:
		if beg + l1 + l2 + l3 == len(s):
			return True
		return rec(s, beg + l1, l2, l3)
	return False

def isAdditiveSequence(num):
	S = str(num)
	for i in range(1, len(S)):
		for j in range(1, len(S) - i):
			if rec(S, 0, i, j):
				return 1
	return 0


def solve(i, nums, s, lst=[]):
	if i >= len(nums) and s <= 2:
		return False
	if i >= len(nums):
		return True
	ans = False
	for j in range(i, len(nums)):
		if s < 2:
			lst.append(nums[i:j + 1])
			ans = ans or solve(j + 1, nums, s + 1, lst)
			lst.pop()
		elif int(nums[i:j + 1]) == int(lst[-1]) + int(lst[-2]):
			lst.append(nums[i:j + 1])
			ans = ans or solve(j + 1, nums, s + 1, lst)
			lst.pop()
	return ans

def isAdditiveSequence(num):
	if solve(0, num, 0):
		return 1
	return 0


def find_seq(n1, n2, s, found):
	if s == '' and found:
		return True
	n3 = str(n1 + n2)
	idx = min(len(s), len(n3))
	if s[:idx] == n3:
		return find_seq(n2, int(n3), s[idx:], True)
	return False

def isAdditiveSequence(num):
	for i in range(1, len(num) - 1):
		n1 = int(num[:i])
		if str(n1) != num[:i]:
			break
		for j in range(i + 1, len(num)):
			n2 = int(num[i:j])
			if str(n2) != num[i:j]:
				break
			found = find_seq(n1, n2, num[j:], False)
			if found:
				return 1
	return 0


def isAdditiveSequence(num):

	def ne(val, k, s):
		for i in range(k + 1, len(s) + 1):
			if int(s[k:i]) == val:
				return i
		return -1

	def ad(prev1, prev2, s):
		if s == '':
			return 1
		if prev1 == 0:
			ret = False
			for i in range(1, len(s) + 1):
				for j in range(i + 1, len(s) + 1):
					tmp = ne(int(s[0:i]) + int(s[i:j]), j, s)
					if tmp != -1:
						ret |= ad(s[i:j], s[j:tmp], s[tmp:])
			return ret
		else:
			tmp = ne(int(prev1) + int(prev2), 0, s)
			if tmp != -1:
				return ad(prev2, s[0:tmp], s[tmp:])
			return False

	def isad(s):
		if ad(0, 0, s):
			return 1
		else:
			return 0
	return isad(num)


def isAdditiveSequence(num):

	def rec(first, second, rest):
		if len(rest) == 0:
			return True
		total = str(first + second)
		l = len(total)
		if total == rest[:l]:
			return rec(second, int(total), rest[l:])
	for i in range(1, len(num) - 1):
		for j in range(i + 1, len(num)):
			first = num[:i]
			second = num[i:j]
			if first[0] == '0' and len(first) > 1 or (second[0] == '0' and len(second) > 1):
				break
			if rec(int(first), int(second), num[j:]):
				return 1
	return 0


def check(num, n, fi, fl, first, si, sl, second):
	n1 = num[fi:fl + 1:1]
	n2 = num[si:sl + 1:1]
	if n1 and n2 and (len(n1) == first) and (len(n2) == second):
		sum = int(int(n1) + int(n2))
		third = len(str(sum))
		ri = sl + 1
		rl = ri + third - 1
		res = num[ri:rl + 1:1]
		if res and int(res) == sum:
			return check(num, n, si, sl, second, ri, rl, third)
		elif not res:
			return True
	else:
		return False

def index(num, n, first, second):
	fi = 0
	fl = first - 1
	si = fl + 1
	sl = si + second - 1
	return check(num, n, fi, fl, first, si, sl, second)

def isAdditiveSequence(num):
	n = len(num)
	first = int(n / 2)
	for i in range(1, first + 1):
		second = int((n - i) / 2)
		for j in range(1, second + 1):
			if index(num, n, i, j):
				return 1
	return 0


def isValid(first, second, others):
	if len(first) > 1 and first[0] == '0' or (len(second) > 1 and second[0] == '0'):
		return 0
	sum_str = str(int(first) + int(second))
	if sum_str == others:
		return 1
	elif others.startswith(sum_str):
		return isValid(second, sum_str, others[len(sum_str):])
	else:
		return 0

def isAdditiveSequence(num):
	length = len(num)
	for i in range(1, length // 2 + 1):
		for j in range(1, length - i // 2 + 1):
			(first, second, others) = (num[:i], num[i:i + j], num[i + j:])
			if isValid(first, second, others):
				return 1
	return 0


def isAdditiveSequence(num):
	for i in range(len(num) // 2):
		a = int(num[:i + 1])
		for j in range(i + 1, len(num) - i - 1):
			b = int(num[i + 1:j + 1])
			summ = str(a + b)
			(idx, flag) = (0, True)
			for k in range(j + 1, len(num)):
				if idx == len(summ):
					if isAdditiveSequence(num[i + 1:]):
						return 1
					flag = False
					break
				if summ[idx] == num[k]:
					idx += 1
				else:
					break
			if idx == len(summ) and flag == True:
				return 1
	return 0


def isAdditiveSequence(num):
	S = num
	A1 = ''
	A2 = ''
	A3 = ''
	Re = ''
	F = False
	for i in range(1, len(S)):
		for j in range(i + 1, len(S)):
			A1 = S[:i]
			A2 = S[i:j]
			A3 = int(A1) + int(A2)
			Re = str(int(A1)) + str(int(A2)) + str(int(A3))
			if Re == S:
				F = True
				break
			else:
				while len(Re) <= len(S) and Re in S:
					(A1, A2) = (A2, A3)
					A3 = int(A1) + int(A2)
					Re = Re + str(int(A3))
					if Re == S:
						F = True
						break
				if F:
					break
		if F:
			break
	if F:
		return 1
	else:
		return 0


def isAdditiveSequence(num):

	def f(a, l1, l2):
		if a == '':
			return 0
		if int(a) == l1 + l2:
			return 1
		for i in range(len(a)):
			if len(a[:i]) > 0 and (int(a[:i]) == l1 + l2 or l2 == 0) and (f(a[i:], int(a[:i]), l1) == 1):
				return 1
		return 0
	return f(str(num), 0, 0)