Additive Number

                                            
class Solution {
public:
    bool isAdditiveNumber(string num) {
        for(int i=1; i<=num.size()/2; i++){
            for(int j=1; j<=(num.size()-i)/2; j++){
                if(helper(num.substr(0, i), num.substr(i, j), num.substr(i+j))) return true;
            }
        }
        return false;
    }
    
    bool helper(string num1, string num2, string num){
        if((num1.size() > 1 && num1[0] == '0') || (num2.size() > 1 && num2[0] == '0')) return false;
        string sum = addStrings(num1, num2);
        if(sum == num) return true;
        if(num.size() <= sum.size() || sum.compare(num.substr(0, sum.size())) != 0) return false;
        else return helper(num2, sum, num.substr(sum.size()));
    }
    
    string addStrings(string num1, string num2){
        string res = "";
        int carry = 0;
        int i = num1.size()-1;
        int j = num2.size()-1;
        while(i >= 0 || j >= 0 || carry > 0){
            int x = (i >= 0) ? num1[i--]-'0' : 0;
            int y = (j >= 0) ? num2[j--]-'0' : 0;
            int sum = x + y + carry;
            res = to_string(sum%10) + res;
            carry = sum/10;
        }
        return res;
    }
};

                                            
public class Solution {
    public bool IsAdditiveNumber(string num) {
        for (int i = 1; i < num.Length; i++) {
            for (int j = i + 1; j < num.Length; j++) {
                string num1 = num.Substring(0, i);
                string num2 = num.Substring(i, j - i);
                if ((num1.Length > 1 && num1[0] == '0') || (num2.Length > 1 && num2[0] == '0')) continue;
                
                long n1 = long.Parse(num1);
                long n2 = long.Parse(num2);
                
                if (IsAdditive(num, j, n1, n2)) return true;
            }
        }
        
        return false;
    }
    
    private bool IsAdditive(string num, int index, long num1, long num2) {
        if (index == num.Length) return true;
        
        long sum = num1 + num2;
        string sumStr = sum.ToString();
        if (index + sumStr.Length > num.Length || !num.Substring(index, sumStr.Length).Equals(sumStr)) return false;
        
        return IsAdditive(num, index + sumStr.Length, num2, sum);
    }
}

                                            
/**
 * @param {string} num
 * @return {boolean}
 */
var isAdditiveNumber = function(num) {
    const isAdditive = (num, num1, num2) => {
        if (num === '') return true;
        if ((num1.length > 1 && num1[0] === '0') || (num2.length > 1 && num2[0] === '0')) return false;
        const sum = (BigInt(num1) + BigInt(num2)).toString();
        if (num.startsWith(sum)) {
            return isAdditive(num.substring(sum.length), num2, sum);
        }
        return false;
    };

    for (let i = 1; i <= num.length / 2; i++) {
        for (let j = 1; j <= (num.length - i) / 2; j++) {
            const num1 = num.substring(0, i);
            const num2 = num.substring(i, i + j);
            if (isAdditive(num.substring(i + j), num1, num2)) return true;
        }
    }

    return false;
};

                                            
function isAdditiveNumber(num: string): boolean {
    function isAdditive(index: number, num1: string, num2: string, remaining: string): boolean {
        if (index === num.length) {
            return remaining.length === 0;
        }

        if ((num1.length > 1 && num1[0] === '0') || (num2.length > 1 && num2[0] === '0')) {
            return false;
        }

        const sum = (+num1) + (+num2);
        const sumStr = sum.toString();

        if (remaining.indexOf(sumStr) !== 0) {
            return false;
        }

        return isAdditive(index + sumStr.length, num2, sumStr, remaining.substring(sumStr.length));
    }

    for (let i = 1; i <= num.length / 2; i++) {
        for (let j = 1; j <= (num.length - i) / 2; j++) {
            if (isAdditive(i + j, num.substring(0, i), num.substring(i, i + j), num.substring(i + j))) {
                return true;
            }
        }
    }

    return false;
};

                                            
func isAdditiveNumber(num string) bool {
    n := len(num)
    for i := 1; i <= n/2; i++ {
        for j := i + 1; j < n; j++ {
            if num[0] == '0' && i > 1 {
                break
            }
            if num[i] == '0' && j > i+1 {
                break
            }
            if isValid(num[:i], num[i:j], num[j:]) {
                return true
            }
        }
    }
    return false
}

func isValid(num1, num2, num string) bool {
    sum := addStrings(num1, num2)
    if sum == num {
        return true
    }
    if len(sum) >= len(num) || sum != num[:len(sum)] {
        return false
    }
    return isValid(num2, sum, num[len(sum):])
}

func addStrings(num1, num2 string) string {
    res := make([]byte, max(len(num1), len(num2))+1)
    carry, idx := 0, len(res)-1
    for i, j := len(num1)-1, len(num2)-1; i >= 0 || j >= 0 || carry > 0; i, j = i-1, j-1 {
        if i >= 0 {
            carry += int(num1[i] - '0')
        }
        if j >= 0 {
            carry += int(num2[j] - '0')
        }
        res[idx] = byte(carry%10) + '0'
        carry /= 10
        idx--
    }
    return string(res[idx+1:])
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

                                            
impl Solution {
    pub fn is_additive_number(num: String) -> bool {
        fn backtrack(num: &str, start: usize, first: i64, second: i64) -> bool {
            if start == num.len() {
                return true;
            }
            for i in start..num.len() {
                if i > start && num.chars().nth(start) == Some('0') {
                    break;
                }
                let cur_str = &num[start..=i];
                let cur_num: i64 = match cur_str.parse() {
                    Ok(num) => num,
                    Err(_) => return false,
                };
                if (first == -1 || second == -1 || first + second == cur_num) && backtrack(num, i + 1, second, cur_num) {
                    return true;
                }
            }
            false
        }

        for i in 1..num.len() {
            if i > 1 && num.chars().nth(0) == Some('0') {
                break;
            }
            let first_str = &num[0..i];
            let first: i64 = match first_str.parse() {
                Ok(num) => num,
                Err(_) => return false,
            };

            for j in i + 1..num.len() {
                if j > i + 1 && num.chars().nth(i) == Some('0') {
                    break;
                }
                let second_str = &num[i..j];
                let second: i64 = match second_str.parse() {
                    Ok(num) => num,
                    Err(_) => return false,
                };
                if backtrack(&num, j, first, second) {
                    return true;
                }
            }
        }

        false
    }
}

To solve this coding challenge, we need to verify if a given string of digits forms an additive sequence. An additive sequence means that starting from any two consecutive numbers, the next number in the series is always the sum of the previous two. The constraints ensure that no number in the sequence starts with a leading zero (except for the number '0' itself), and the sequence must contain at least three numbers. Here’s a step-by-step breakdown of how to approach and solve this problem:

Explanation

The problem can be approached with a recursive function to check for all possible combinations of initial numbers and verify if they form an additive sequence. Here’s the plan:

Split the string into initial numbers : We iterate through potential pairs of starting numbers. The first loop picks the length of the first number, and the second loop picks the length of the second number.
Generate the next number in the sequence : For each pair of starting numbers, compute the third number in the series by adding the first two numbers.
Check for validity and recursion : If the starting numbers and subsequent sum lead to the sequence correctly matching the input string, recursively check the remainder of the string.
Handle leading zeros : If any of the numbers formed (except '0' itself) has a leading zero, it’s immediately invalid.
Return the results : If any valid sequence is found during the iterations, return true. If no valid sequences are found after all iterations, return false.

Pseudocode with Comments

We’ll use a helper function

isAdditive

to verify if the sequence continues correctly from a given pair of numbers.

                                            
# Main function to check if the string can form an additive number sequence
function isAdditiveNumber(input_number):

# Function to check recursively if the rest of the string follows the additive sequence
function isAdditive(remaining_string, num1, num2):

# Base case: if the remaining string is empty, we have a valid sequence
if remaining_string == "":
return True

# Prevent invalid sequences by checking for leading zeros
if (length(num1) > 1 and num1[0] == '0') or (length(num2) > 1 and num2[0] == '0'):
return False

# Compute the sum of num1 and num2
sum_value = toString(toBigInt(num1) + toBigInt(num2))

# Check if the remaining string starts with this sum value
if startsWith(remaining_string, sum_value):
# Recur with the remaining string after the sum value, and the new pair is (num2, sum_value)
return isAdditive(substring(remaining_string, length(sum_value)), num2, sum_value)

# If the sequence does not match, return False
return False

# Try all pairs of first and second numbers
for i from 1 to length(input_number) / 2:
for j from 1 to (length(input_number) - i) / 2:
num1 = substring(input_number, 0, i)
num2 = substring(input_number, i, i + j)

# Check if this pair can start a valid additive sequence
if isAdditive(substring(input_number, i + j), num1, num2):
return True

# If no valid sequence is found after all iterations, return False
return False

Step-by-Step Explanation / Detailed Steps in Pseudocode

Start the main function
isAdditiveNumber

with the input string.
Define the helper function
isAdditive

which takes a
remaining_string

,
num1

, and
num2

. This function will check if the sequence can continue correctly starting from
num1

and
num2

.
In
isAdditive

, first check if the
remaining_string

is empty. If it is, this indicates the entire string has been successfully parsed into an additive sequence, so return true.
Check for any leading zeros in
num1

or
num2

(except for the number '0' itself). If a leading zero is found, return false to indicate this sequence is invalid.
Calculate the sum of
num1

and
num2

, and convert this sum back to a string.
Check if the
remaining_string

starts with this computed sum. If it does, make a recursive call to
isAdditive

with the remaining part of the string after removing the matched sum, while setting
num2

and
sum_value

as the next pair to check.
If the sequence doesn’t match, return false from
isAdditive

.
Back in the main function, iterate through all possible pairs of starting numbers by adjusting the lengths of
num1

and
num2

using two nested loops.
For each potential pair, call
isAdditive

and check if it returns true. If it does, return true from the main function.
If no valid sequence is found after all iterations, return false, indicating that the input string is not an additive number sequence.

This detailed methodology ensures that the function thoroughly explores all possible additive sequences while adhering to the constraints and rules of the problem.