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.
Note: Numbers in the additive sequence cannot have leading zeros.

Explanation:

Python: Find whether it contains an additive sequence or not

Sample Solution:

Python Code:

class Solution(object):
# DFS: iterative implement.
    def is_additive_number(self, num):
        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__":
    print(Solution().is_additive_number('66121830'))
    print(Solution().is_additive_number('51123'))
    print(Solution().is_additive_number('235813'))
	

Sample Output:

True
False  
True

Flowchart:

Python Flowchart: Find whether it contains an additive sequence or not

Python Code Editor:

Contribute your code and comments through Disqus.

Previous: Write a Python program to add the digits of a positive integer repeatedly until the result has a single digit.
Next: Write a Python program to reverse the digits of an integer.

What is the difficulty level of this exercise?

Test your Programming skills with w3resource's quiz.



Become a Patron!

Follow us on Facebook and Twitter for latest update.

It will be nice if you may share this link in any developer community or anywhere else, from where other developers may find this content. Thanks.

https://198.211.115.131/python-exercises/challenges/1/python-challenges-1-exercise-17.php