306. Additive Number – Leetcode Solutions

Example 1:

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:

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

class Solution:
    def isAdditiveNumber(self, num: str) -> bool:
        # Helper function to check if a string can represent a valid number
        # It checks that the number doesn't have a leading zero unless it's '0'
        def isValidNumber(number: str) -> bool:
            return not (len(number) > 1 and number[0] == '0')

        # Main function that checks whether the string forms a valid additive sequence
        n = len(num)
        
        # Try every possible combination of the first two numbers
        for i in range(1, n):
            for j in range(i + 1, n):
                # First number is num[:i], second number is num[i:j]
                num1, num2 = num[:i], num[i:j]

                # Check if both numbers are valid (no leading zeros)
                if not isValidNumber(num1) or not isValidNumber(num2):
                    continue

                # Convert these numbers to integers
                x1, x2 = int(num1), int(num2)

                # Use the remaining part of the string to check if it forms an additive sequence
                k = j
                while k < n:
                    # Calculate the next number in the sequence
                    x3 = x1 + x2

                    # Convert this number to a string
                    x3_str = str(x3)

                    # Check if the next part of the string matches this number
                    if not num.startswith(x3_str, k):
                        break

                    # Move the pointers: shift x1, x2 to the next numbers
                    k += len(x3_str)
                    x1, x2 = x2, x3

                # If we have used the entire string and formed a valid sequence, return True
                if k == n:
                    return True

        # If no valid sequence was found, return False
        return False

class Solution {
public:
    // Helper function to check if two numbers can form a valid additive sequence
    bool isValid(string num, int start, int len1, int len2) {
        // If the first number has a leading zero and its length is greater than 1, it's invalid
        if (num[start] == '0' && len1 > 1) return false;
        // If the second number has a leading zero and its length is greater than 1, it's invalid
        if (num[start + len1] == '0' && len2 > 1) return false;
        
        // Convert the first and second parts of the string into numbers
        string num1 = num.substr(start, len1);
        string num2 = num.substr(start + len1, len2);
        
        // Start checking from the third part
        long long a = stoll(num1);
        long long b = stoll(num2);
        string sumStr;
        
        for (int i = start + len1 + len2; i < num.size(); i += sumStr.size()) {
            // Compute the sum of the previous two numbers
            long long sum = a + b;
            sumStr = to_string(sum);
            
            // If the remaining part of the string does not start with the computed sum, return false
            if (num.substr(i, sumStr.size()) != sumStr) return false;
            
            // Update a and b for the next iteration
            a = b;
            b = sum;
        }
        
        // If the loop completes without issues, it's a valid additive sequence
        return true;
    }

    bool isAdditiveNumber(string num) {
        int n = num.size();
        
        // We need at least 3 numbers for a valid sequence
        // Try different lengths for the first and second numbers
        for (int len1 = 1; len1 <= n / 2; ++len1) {
            for (int len2 = 1; max(len1, len2) <= n - len1 - len2; ++len2) {
                // Check if the numbers formed by the first len1 and len2 digits can create an additive sequence
                if (isValid(num, 0, len1, len2)) {
                    return true;
                }
            }
        }
        
        // If no valid sequence is found, return false
        return false;
    }
};

function isValid(num, start, len1, len2) {
    // If the first number has a leading zero and it's longer than 1 digit, it's invalid
    if (num[start] === '0' && len1 > 1) return false;
    // If the second number has a leading zero and it's longer than 1 digit, it's invalid
    if (num[start + len1] === '0' && len2 > 1) return false;

    // Extract the first and second numbers from the string
    let num1 = num.substring(start, start + len1);
    let num2 = num.substring(start + len1, start + len1 + len2);

    // Convert them to integers
    let a = BigInt(num1);
    let b = BigInt(num2);
    
    // Iterate through the rest of the string to verify the sequence
    for (let i = start + len1 + len2; i < num.length;) {
        // Calculate the sum of the previous two numbers
        let sum = a + b;
        let sumStr = sum.toString();  // Convert the sum to a string

        // If the next part of the string doesn't match the calculated sum, return false
        if (!num.startsWith(sumStr, i)) return false;

        // Update a and b to the next two numbers in the sequence
        a = b;
        b = sum;

        // Move the index forward by the length of the sum
        i += sumStr.length;
    }

    // If we reach this point, it means the sequence is valid
    return true;
}


var isAdditiveNumber = function(num) {
    let n = num.length;

    // We need at least 3 numbers to form a valid additive sequence
    // Try different lengths for the first and second numbers
    for (let len1 = 1; len1 <= Math.floor(n / 2); len1++) {
        for (let len2 = 1; Math.max(len1, len2) <= n - len1 - len2; len2++) {
            // Check if the first two numbers (with lengths len1 and len2) can form a valid additive sequence
            if (isValid(num, 0, len1, len2)) {
                return true;  // If a valid sequence is found, return true
            }
        }
    }

    // If no valid sequence is found, return false
    return false;
};

class Solution {

    // Helper function to check if the sequence formed by the first two numbers is valid
    private boolean isValid(String num, int start, int len1, int len2) {
        // If the first number has a leading zero and its length is greater than 1, it's invalid
        if (num.charAt(start) == '0' && len1 > 1) return false;
        // If the second number has a leading zero and its length is greater than 1, it's invalid
        if (num.charAt(start + len1) == '0' && len2 > 1) return false;

        // Extract the first two numbers as substrings
        String num1 = num.substring(start, start + len1);
        String num2 = num.substring(start + len1, start + len1 + len2);

        // Convert the extracted numbers to long to avoid overflow
        long a = Long.parseLong(num1);
        long b = Long.parseLong(num2);
        
        // Start checking from the third number onward
        for (int i = start + len1 + len2; i < num.length();) {
            // Calculate the sum of the previous two numbers
            long sum = a + b;
            // Convert the sum to a string
            String sumStr = Long.toString(sum);
            
            // If the remaining part of the string doesn't start with the sum, return false
            if (!num.startsWith(sumStr, i)) return false;

            // Move the pointers forward for the next iteration
            a = b;
            b = sum;
            i += sumStr.length();
        }

        // If all numbers match the expected sums, return true
        return true;
    }

    public boolean isAdditiveNumber(String num) {
        int n = num.length();

        // Try different lengths for the first and second numbers
        // The maximum length for the first number is n / 2, and for the second number, it depends on the remaining digits
        for (int len1 = 1; len1 <= n / 2; len1++) {
            for (int len2 = 1; Math.max(len1, len2) <= n - len1 - len2; len2++) {
                // Check if a valid additive sequence can be formed with the first two numbers
                if (isValid(num, 0, len1, len2)) {
                    return true; // Return true if a valid sequence is found
                }
            }
        }

        // If no valid sequence is found, return false
        return false;
    }
}