Welcome to Subscribe On Youtube
306. Additive Number
Description
An additive number is a string whose digits can form an additive sequence.
A valid additive sequence should contain at least three numbers. Except for the first two numbers, each subsequent number in the sequence must be the sum of the preceding two.
Given a string containing only digits, return true if it is an additive number or false otherwise.
Note: Numbers in the additive sequence cannot have leading zeros, so sequence 1, 2, 03 or 1, 02, 3 is invalid.
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
Constraints:
1 <= num.length <= 35numconsists only of digits.
Follow up: How would you handle overflow for very large input integers?
Solutions
Let the first digit start with one digit, and the second digit will be searched for higher digits. The first two digits are confirmed, and the third digit is obtained by adding them.
The three arrays are arranged to form a string, which is the same length as the original string if it is less than the original length, then take out the second and third numbers from the previous calculation, and use the same method to get the third number, then add the current string, and then sum Compared to the original string length.
Follow up: How would you handle overflow for very large input integers?
Handling very large input integers that exceed the maximum value representable by native data types (e.g., int or long in Python) requires a strategy to avoid overflow. Here’s an approach to handle such cases:
Handling Overflow
To manage very large integers that could potentially cause overflow, you can perform arithmetic operations as string manipulations. This means converting the numerical addition operation into a character-by-character addition, similar to how you would manually add numbers on paper. This approach eliminates the risk of overflow by not relying on the numerical limits of the data types.
Implementation Strategy
-
String Addition Function: Implement a function to add two large numbers represented as strings. This function should handle carrying over digits for sums greater than 9 and return the sum as a string.
-
Modified Additive Check: Use the string addition function within the logic that checks if the given number is an additive sequence. Iterate through possible first and second numbers, represented as substrings, and use the addition function to generate each subsequent number. Compare the generated number with the next part of the main string to see if the sequence continues correctly.
-
Edge Cases: Ensure the initial two numbers do not
start with a zerounless they are actually zero, as per the problem’s definition of an additive sequence. Also, handle cases where the generated sequence correctly ends at the end of the main string.
-
class Solution { public boolean isAdditiveNumber(String num) { int n = num.length(); for (int i = 1; i < Math.min(n - 1, 19); ++i) { for (int j = i + 1; j < Math.min(n, i + 19); ++j) { if (i > 1 && num.charAt(0) == '0') { break; } if (j - i > 1 && num.charAt(i) == '0') { continue; } long a = Long.parseLong(num.substring(0, i)); long b = Long.parseLong(num.substring(i, j)); if (dfs(a, b, num.substring(j))) { return true; } } } return false; } private boolean dfs(long a, long b, String num) { if ("".equals(num)) { return true; } if (a + b > 0 && num.charAt(0) == '0') { return false; } for (int i = 1; i < Math.min(num.length() + 1, 19); ++i) { if (a + b == Long.parseLong(num.substring(0, i))) { if (dfs(b, a + b, num.substring(i))) { return true; } } } return false; } } -
class Solution { public: bool isAdditiveNumber(string num) { int n = num.size(); for (int i = 1; i < min(n - 1, 19); ++i) { for (int j = i + 1; j < min(n, i + 19); ++j) { if (i > 1 && num[0] == '0') break; if (j - i > 1 && num[i] == '0') continue; auto a = stoll(num.substr(0, i)); auto b = stoll(num.substr(i, j - i)); if (dfs(a, b, num.substr(j, n - j))) return true; } } return false; } bool dfs(long long a, long long b, string num) { if (num == "") return true; if (a + b > 0 && num[0] == '0') return false; for (int i = 1; i < min((int) num.size() + 1, 19); ++i) if (a + b == stoll(num.substr(0, i))) if (dfs(b, a + b, num.substr(i, num.size() - i))) return true; return false; } }; -
class Solution: def isAdditiveNumber(self, num: str) -> bool: def dfs(startIndex: int, out: List[int]) -> bool: # equal check is here if len(out) >= 3 and out[-1] != out[-2] + out[-3]: return False if startIndex == len(num): return len(out) >= 3 for i in range(startIndex, len(num)): current = num[startIndex: i + 1] if (len(current) > 1 and current[0] == '0'): break out.append(int(current)) if dfs(i + 1, out): return True out.pop() return False if not num: return False return dfs(0, []) ############# # follow up: super large number, solve overflow issue class Solution: def addStrings(num1: str, num2: str) -> str: carry = 0 result = [] i, j = len(num1) - 1, len(num2) - 1 while i >= 0 or j >= 0 or carry: x = int(num1[i]) if i >= 0 else 0 y = int(num2[j]) if j >= 0 else 0 sum = x + y + carry result.append(str(sum % 10)) carry = sum // 10 i, j = i - 1, j - 1 return ''.join(reversed(result)) def isAdditiveNumber(num: str) -> bool: n = len(num) for i in range(1, n): for j in range(i+1, n): num1, num2 = num[:i], num[i:j] if (len(num1) > 1 and num1[0] == '0') or (len(num2) > 1 and num2[0] == '0'): continue while j < n: sum = addStrings(num1, num2) if not num.startswith(sum, j): break j += len(sum) num1, num2 = num2, sum if j == n: return True return False ############# class Solution: def isAdditiveNumber(self, num: str) -> bool: def dfs(a, b, num): if not num: return True if a + b > 0 and num[0] == '0': return False for i in range(1, len(num) + 1): if a + b == int(num[:i]): if dfs(b, a + b, num[i:]): return True return False n = len(num) for i in range(1, n - 1): # 1st cut if i > 1 and num[0] == '0': # 0 + 1 = 1 is fine, but 00 + 1 is wrong break for j in range(i + 1, n): # 2nd cut, so making it a 3-segments if j - i > 1 and num[i] == '0': break if dfs(int(num[:i]), int(num[i:j]), num[j:]): # better than below, early stop return True return False -
func isAdditiveNumber(num string) bool { n := len(num) var dfs func(a, b int64, num string) bool dfs = func(a, b int64, num string) bool { if num == "" { return true } if a+b > 0 && num[0] == '0' { return false } for i := 1; i < min(len(num)+1, 19); i++ { c, _ := strconv.ParseInt(num[:i], 10, 64) if a+b == c { if dfs(b, c, num[i:]) { return true } } } return false } for i := 1; i < min(n-1, 19); i++ { for j := i + 1; j < min(n, i+19); j++ { if i > 1 && num[0] == '0' { break } if j-i > 1 && num[i] == '0' { continue } a, _ := strconv.ParseInt(num[:i], 10, 64) b, _ := strconv.ParseInt(num[i:j], 10, 64) if dfs(a, b, num[j:]) { return true } } } return false }