Additive Number - Practice Coding Problems

Additive Number - Problem

String Backtracking Medium

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.

Input & Output

Example 1 — Valid Additive Number

$ Input: num = "112358"

› Output: true

💡 Note: The digits can form additive sequence: 1, 1, 2, 3, 5, 8. 1+1=2, 1+2=3, 2+3=5, 3+5=8

Example 2 — Invalid Sequence

$ Input: num = "199100199"

› Output: true

💡 Note: The additive sequence is: 1, 99, 100, 199. 1+99=100, 99+100=199

Example 3 — No Valid Sequence

$ Input: num = "1023"

› Output: false

💡 Note: Cannot form a valid additive sequence without leading zeros

Constraints

1 ≤ num.length ≤ 35
num consists only of digits

Visualization

Tap to expand

Understanding the Visualization

Input

String of digits "112358"

Process

Try different ways to split into additive sequence

Output

Return true if valid sequence exists

Key Takeaway

🎯 Key Insight: Once you pick the first two numbers, the entire additive sequence is uniquely determined

Asked in

G Google 35 f Facebook 28 a Amazon 22 M Microsoft 18

The key insight is that once you choose the first two numbers in an additive sequence, the rest of the sequence is completely determined. Use backtracking to try all possible ways to split the string into the first two numbers, then recursively verify if the remaining digits form a valid additive sequence. Best approach uses optimized backtracking with pruning. Time: O(n³), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Splits	O(n³)	O(n)	Try every possible way to split the string into first two numbers, then check if rest forms valid sequence
Optimized Backtracking with Pruning	O(n³)	O(n)	Enhanced backtracking with better pruning conditions and optimized string operations
Backtracking with Early Termination	O(n³)	O(n)	Use backtracking to build the sequence step by step with early termination when invalid

Brute Force - Try All Splits — Algorithm Steps

Step 1: Try all possible lengths for first number (1 to n/2)
Step 2: Try all possible lengths for second number (1 to remaining/2)
Step 3: Check if rest of string forms valid additive sequence
Step 4: Return true if any combination works

Visualization

Tap to expand

Step-by-Step Walkthrough

Split Selection

Try all positions to split first two numbers

Validation

Check if remaining string forms valid sequence

Result

Return true if any split works

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool isValidNumber(const char* s, int len) {
    return s[0] != '0' || len == 1;
}

char* addStrings(const char* num1, const char* num2) {
    int len1 = strlen(num1);
    int len2 = strlen(num2);
    int maxLen = len1 > len2 ? len1 + 2 : len2 + 2;
    char* result = (char*)malloc(maxLen);
    
    int carry = 0;
    int i = len1 - 1;
    int j = len2 - 1;
    int k = 0;
    
    while (i >= 0 || j >= 0 || carry) {
        int sum = carry;
        if (i >= 0) sum += num1[i--] - '0';
        if (j >= 0) sum += num2[j--] - '0';
        result[k++] = sum % 10 + '0';
        carry = sum / 10;
    }
    
    result[k] = '\0';
    
    // Reverse the string
    for (int l = 0; l < k / 2; l++) {
        char temp = result[l];
        result[l] = result[k - 1 - l];
        result[k - 1 - l] = temp;
    }
    
    return result;
}

bool checkAdditive(const char* num1, const char* num2, const char* remaining) {
    if (strlen(remaining) == 0) return true;
    
    char* expected = addStrings(num1, num2);
    int expectedLen = strlen(expected);
    
    if (strncmp(remaining, expected, expectedLen) != 0) {
        free(expected);
        return false;
    }
    
    bool result = checkAdditive(num2, expected, remaining + expectedLen);
    free(expected);
    return result;
}

bool solution(const char* num) {
    int n = strlen(num);
    
    for (int i = 1; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            char num1[20], num2[20];
            strncpy(num1, num, i);
            num1[i] = '\0';
            strncpy(num2, num + i, j - i);
            num2[j - i] = '\0';
            
            if (!isValidNumber(num1, i) || !isValidNumber(num2, j - i)) continue;
            
            if (checkAdditive(num1, num2, num + j)) {
                return true;
            }
        }
    }
    
    return false;
}

int main() {
    char num[100];
    fgets(num, sizeof(num), stdin);
    num[strcspn(num, "\n")] = 0;
    
    bool result = solution(num);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

Two nested loops for splits (O(n²)) and string operations for validation (O(n))

⚠ Quadratic Growth

Space Complexity

O(n)

String concatenation and number parsing creates temporary strings

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~25 min Avg. Time

756 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Splits — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler