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:
Define a recursive helper function that takes in three parameters: the remaining string
num
, the current indexidx
being processed, and the two previous numbersprev1
andprev2
that were added together to get the current number.Base Case:
a. If the index
idx
reaches the end of the string and we have at least three numbers in the sequence, we returnTrue
.b. If the index
idx
reaches the end of the string but we have less than three numbers in the sequence, we returnFalse
.For each possible length of the current number
cur_len
starting from indexidx
, we check whether the current number is equal to the sum ofprev1
andprev2
.If the current number is equal to the sum of
prev1
andprev2
, we recursively call the helper function with the updated parameters: the remaining string from indexidx+cur_len
,idx+cur_len
as the new starting index, andprev2
andcur
as the new previous numbers.If any of the recursive calls return
True
, we returnTrue
from the current call. If none of them returnTrue
, we try the next possible length ofcur_len
.If all possible lengths of
cur_len
have been tried and none of them returnedTrue
, we returnFalse
.
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); } }