blob: 8f0bbc99ee0aa5a6b0751b381296bbfc541b4e04 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
|
## Remarks
## https://www.geeksforgeeks.org/string-with-additive-sequence-set-2/
## python3 code to implement the approach
## Variable to store the result
bResult = False
arrStr = []
## Function to check the additive sequence
def check_additive(strIn, subStrIn):
global bResult
global arrStr
## If the end is reached and vector consists of more than 2 numbers, then one of the possible solution is found
if (subStrIn == len(strIn) and len(arrStr) > 2):
## Mark the bResult as true to indicate the solution is found and to avoid for trying the rest of the combinations
bResult = True
return
nInt_01, nInt_02, nInt_03 = 0, 0, 0
if (len(arrStr) >= 2):
## Store the previous two numbers of the sequence to check the additive sequence property for the next number
nInt_02 = arrStr[len(arrStr) - 1]
nInt_01 = arrStr[len(arrStr) - 2]
for nIndxLoop in range(subStrIn, len(strIn)):
## Generate the number
nInt_03 = nInt_03 * 10 + ord(strIn[nIndxLoop]) - ord("0")
## Try all the possible ways to generate the first two numbers
## i.e. if vector consists of less than two numbers and no solution is found yet
if (len(arrStr) < 2):
arrStr.append(nInt_03)
check_additive(strIn, nIndxLoop + 1)
## Pop the value to try for the other combination
arrStr.pop()
## If the number generated so far is not equal the sum of previous two numbers in the sequence
## then it cannot be a part of additive sequence hence no need to proceed further
return
if (nInt_03 != nInt_01 + nInt_02):
return
## If the number generated so far is equal to the sum of previous two numbers
## then it can be a part of additive sequence
## push it into vector and check for remaining string
## Store it in the vector
arrStr.append(nInt_03)
## Recur for remaining string
check_additive(strIn, nIndxLoop + 1)
## If unable to find solution
## pop it and try for other combination
arrStr.pop()
return
## Function to check if additive sequence
def IsAdditiveSeq(strInputFunc):
global bResult
## In order to form additive sequence, the length of the string must be at least three
if (len(strInputFunc) <= 2):
return False
bResult = False
check_additive(strInputFunc, 0)
return bResult
## Driver Code
if __name__ == "__main__":
## strInput = "112358" ## Example 1
## strInput = "12345" ## Example 2
strInput = "199100199" ## Example 3
print (IsAdditiveSeq(strInput))
|
