## Similar Problems

### Valid Phone Numbers

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 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 {
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' and len(first) > 1 or second == '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

return False```
```var isAdditiveNumber = function(num) {

};```
```class Solution {
public:
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' || num2.size() > 1 && num2 == '0') return false;
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 {
int len = num.Length;
for (int i = 1; i <= len / 2; i++) {
if (num == '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);
}
}```

## Top 100 Leetcode Practice Problems In Java

Get 30% Off Instantly!
[gravityforms id="5" description="false" titla="false" ajax="true"]