Problem

An additive number is a string whose digits can form an additive sequence.

A valid additive sequence should contain at least three numbers. Except for the first two numbers, each subsequent number in the sequence must be the sum of the preceding two.

Given a string containing only digits, return true if it is an additive number or false otherwise.

Note: Numbers in the additive sequence cannot have leading zeros, so sequence 1, 2, 03 or 1, 02, 3 is invalid.

Examples

Example 1:

1
2
3
4
5

Input: "112358"
Output: true
Explanation: 
The digits can form an additive sequence: 1, 1, 2, 3, 5, 8. 
1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8

Example 2:

1
2
3
4
5

Input: "199100199"
Output: true
Explanation: 
The additive sequence is: 1, 99, 100, 199. 
1 + 99 = 100, 99 + 100 = 199

Solution

Method 1 - Iteration

To check if a given string is an additive number, we need to iterate through possible pairs of the first two numbers and then check if the rest of the string can form a valid additive sequence.

Here is the approach:

  • Use nested loops to generate the first two numbers, num1 and num2.
  • Ensure no leading zeros unless the number itself is zero.
  • Generate the subsequent numbers in the additive sequence and check if they match the rest of the string.
  • If a valid sequence is found, return true.

A helper function can be used to handle the formation and validation of the sequence once the first two numbers are fixed.

Code

 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

public class Solution {
    public boolean isAdditiveNumber(String num) {
        int n = num.length();
        
        for (int i = 1; i <= n / 2; i++) {
            if (num.charAt(0) == '0' && i > 1) return false;  // Skip leading zero in first number
            long num1 = Long.parseLong(num.substring(0, i));
            
            for (int j = i + 1; j < n; j++) {
                if (num.charAt(i) == '0' && j - i > 1) break;  // Skip leading zero in second number
                long num2 = Long.parseLong(num.substring(i, j));
                
                if (isValid(num, num1, num2, j)) return true;
            }
        }
        return false;
    }
    
    private boolean isValid(String num, long num1, long num2, int start) {
        while (start != num.length()) {
            num2 = num2 + num1;
            num1 = num2 - num1;
            String sum = String.valueOf(num2);
            if (!num.startsWith(sum, start)) return false;
            start += sum.length();
        }
        return true;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution:
    def isAdditiveNumber(self, num: str) -> bool:
        def is_valid(num: str, num1: int, num2: int, start: int) -> bool:
            while start != len(num):
                num2, num1 = num2 + num1, num2
                sum_str = str(num2)
                if not num.startswith(sum_str, start):
                    return False
                start += len(sum_str)
            return True
        
        n: int = len(num)
        for i in range(1, n // 2 + 1):
            if num[0] == '0' and i > 1:  # Avoid leading zero in first number
                return False
            num1: int = int(num[:i])
            for j in range(i + 1, n):
                if num[i] == '0' and j - i > 1:  # Avoid leading zero in second number
                    break
                num2: int = int(num[i:j])
                if is_valid(num, num1, num2, j):
                    return True
        return False

Complexity

  • ⏰ Time complexity: O(n^3) due to the nested loop iterating over potential pairs and the subsequent string comparisons.
  • 🧺 Space complexity: O(n) for storing the numbers and subsequences being checked.