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

Last update on December 21 2024 07:49:28 (UTC/GMT +8 hours)

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:

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 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.