﻿ Python Challenges: Find whether it contains an additive sequence or not - w3resource

# Python Challenges: Find whether it contains an additive sequence or not

## Python Challenges - 1: Exercise-17 with Solution

Write a Python program to find whether it contains an additive sequence or not.

The additive sequence is a sequence of numbers where the sum of the first two numbers is equal to the third one.

Explanation:

Sample Solution:-

Python Code:

``````class Solution(object):
# DFS: iterative implement.
length = len(num)
for i in range(1, int(length/2+1)):
for j in range(1, int((length-i)/2 + 1)):
first, second, others = num[:i], num[i:i+j], num[i+j:]
if self.isValid(first, second, others):
return True
return False

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

if __name__ == "__main__":
```
```

Sample Output:

```True
False
True
```

Flowchart:

Python Code Editor:

```class Solution(object):
# DFS: iterative implement.
length = len(num)
for i in range(1, int(length/2+1)):
for j in range(1, int((length-i)/2 + 1)):
first, second, others = num[:i], num[i:i+j], num[i+j:]
if self.isValid(first, second, others):
return True
return False

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

if __name__ == "__main__":