Solution For Additive Number

Additive Number Problem on Leetcode:

The Additive Number problem on Leetcode requires us to determine whether a given string can be split into a sequence of numbers such that the sum of any two adjacent numbers is equal to the next number in the sequence.

For example, “112358” can be split into [1,1,2,3,5,8] because 1+1=2, 1+2=3, 2+3=5, and 3+5=8.

To solve this problem, we can use a recursive approach where we start with the first and second numbers in the string and check whether they add up to a valid number. Then, if the sum is valid, we move on to the rest of the string recursively until we reach the end.

Here’s the algorithm:

1. Define a recursive helper function that takes in three parameters: the remaining string num, the current index idx being processed, and the two previous numbers prev1 and prev2 that were added together to get the current number.

2. Base Case:

   a. If the index idx reaches the end of the string and we have at least three numbers in the sequence, we return True.

   b. If the index idx reaches the end of the string but we have less than three numbers in the sequence, we return False.

3. For each possible length of the current number cur_len starting from index idx, we check whether the current number is equal to the sum of prev1 and prev2.

4. If the current number is equal to the sum of prev1 and prev2, we recursively call the helper function with the updated parameters: the remaining string from index idx+cur_len, idx+cur_len as the new starting index, and prev2 and cur as the new previous numbers.

5. If any of the recursive calls return True, we return True from the current call. If none of them return True, we try the next possible length of cur_len.

6. If all possible lengths of cur_len have been tried and none of them returned True, we return False.

Here’s the code implementation:

“`
def isAdditiveNumber(num):
def helper(num, idx, prev1, prev2):
if idx == len(num) and len(seq) >= 3:
return True
elif idx == len(num):
return False
else:
cur_len = 1
while idx + cur_len <= len(num):
cur = int(num[idx:idx+cur_len])
if len(str(cur)) != cur_len:
return False
if len(seq) <= 1 or prev1 + prev2 == cur:
if helper(num, idx+cur_len, prev2, cur):
return True
cur_len += 1
return False

for i in range(1, len(num)):
    for j in range(i+1, len(num)):
        seq = [int(num[:i]), int(num[i:j])]
        if helper(num, j, seq[-2], seq[-1]):
            return True
return False

“`

The outer loop starts at index 1 because the first number cannot be of size 0. The inner loop starts at index i+1 to ensure that the second number is longer than the first.

We initialize the sequence of numbers seq with the first two numbers and call the helper function starting at index j where j is the length of the second number. We pass in the previous two numbers as prev2 and prev1 so that they can be used to calculate the current number.

If the helper function returns True, we have found a valid Additive number sequence and return True. If none of the combinations of the first two numbers work, we return False.

The time complexity of this solution is O(n^3) because the outer loop and inner loop go up to n, and for each combination of the first two numbers, the recursive helper function checks all possible lengths of the current number.

Step by Step Implementation For Additive Number

public class Solution {
    public boolean isAdditiveNumber(String num) {
        int n = num.length();
        for (int i = 1; i <= n / 2; ++i)
            for (int j = 1; j <= (n - i) / 2; ++j)
                if (isValid(i, j, num)) return true;
        return false;
    }
    private boolean isValid(int i, int j, String num) {
        if (num.charAt(0) == '0' && i > 1) return false;
        if (num.charAt(i) == '0' && j > 1) return false;
        String sum;
        Long x1 = Long.parseLong(num.substring(0, i));
        Long x2 = Long.parseLong(num.substring(i, i + j));
        for (int start = i + j; start != num.length(); start += sum.length()) {
            x2 = x1 + x2;
            x1 = x2 - x1;
            sum = x2.toString();
            if (!num.startsWith(sum, start)) return false;
        }
        return true;
    }
}

def isAdditiveNumber(num):
    """
    :type num: str
    :rtype: bool
    """
    # base case
    if len(num) < 3:
        return False
    
    # iterate through the string, starting at the first character
    for i in range(len(num) - 2):
        # the first number can be of any length from 1 to len(num)-2
        for j in range(i+1, len(num) - 1):
            # the second number can be of any length from 1 to len(num)-1
            # (as long as it's longer than the first number)
            first = num[i:j]
            second = num[j:k]
            
            # if the first or second number is not valid, continue
            if first[0] == '0' and len(first) > 1 or second[0] == '0' and len(second) > 1:
                continue
                
            # compute the sum of the first and second numbers
            sum = str(int(first) + int(second))
            
            # if the sum is not equal to the remaining part of the string, continue
            if not num.startswith(sum, k):
                continue
            
            # if we reach this point, then we have found a valid additive number
            return True
    
    # if we reach this point, then we have not found a valid additive number
    return False

var isAdditiveNumber = function(num) {
    
};

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 (check(num.substr(0, i), num.substr(i, j), num.substr(i + j))) return true;
            }
        }
        return false;
    }
    bool check(string num1, string num2, string num) {
        if (num1.size() > 1 && num1[0] == '0' || num2.size() > 1 && num2[0] == '0') return false;
        string sum = add(num1, num2);
        if (num == sum) return true;
        if (num.size() <= sum.size() || sum != num.substr(0, sum.size())) return false;
        else return check(num2, sum, num.substr(sum.size()));
    }
    string add(string n, string m) {
        string res;
        int i = n.size() - 1, j = m.size() - 1, carry = 0;
        while (i >= 0 || j >= 0 || carry) {
            int sum = (i >= 0 ? (n[i--] - '0') : 0) + (j >= 0 ? (m[j--] - '0') : 0) + carry;
            res.push_back(sum % 10 + '0');
            carry = sum / 10;
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

using System; 

public class Solution {
    public bool IsAdditiveNumber(string num) {
        int len = num.Length; 
        for (int i = 1; i <= len / 2; i++) {
            if (num[0] == '0' && i > 1) return false; 
            long x1 = Convert.ToInt64(num.Substring(0, i)); 
            for (int j = 1; Math.Max(j, i) <= len - i - j; j++) {
                if (num[i] == '0' && j > 1) break; 
                long x2 = Convert.ToInt64(num.Substring(i, j)); 
                if (isValid(x1, x2, j + i, num)) return true; 
            }
        }
        return false; 
    }
    
    private bool isValid(long x1, long x2, int start, string num) {
        if (start == num.Length) return true; 
        long sum = x1 + x2; 
        string s = sum.ToString(); 
        return num.Substring(start).StartsWith(s) && isValid(x2, sum, start + s.Length, num); 
    }
}