In this guide, you will get 306. Additive NumberLeetCode Solution with the best time and space complexity. The solution to Additive Number problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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
1 <= num.length <= 35
num consists only of digits.
Follow up: How would you handle overflow for very large input integers?
Complexity Analysis
Time Complexity: O(n^2)
Space Complexity: O(n)
306. Additive NumberLeetCode Solution in C++
class Solution {
public:
bool isAdditiveNumber(string num) {
const int n = num.length();
// num[0..i] = firstNum
for (int i = 0; i < n / 2; ++i) {
if (i > 0 && num[0] == '0')
return false;
const long firstNum = stol(num.substr(0, i + 1));
// num[i + 1..j] = secondNum
// |thirdNum| >= max(|firstNum|, |secondNum|)
for (int j = i + 1; max(i, j - i) < n - j; ++j) {
if (j > i + 1 && num[i + 1] == '0')
break;
const long secondNum = stol(num.substr(i + 1, j - i));
if (dfs(num, firstNum, secondNum, j + 1))
return true;
}
}
return false;
}
private:
bool dfs(const string& num, long firstNum, long secondNum, long s) {
if (s == num.length())
return true;
const long thirdNum = firstNum + secondNum;
const string& thirdNumStr = to_string(thirdNum);
return num.find(thirdNumStr, s) == s &&
dfs(num, secondNum, thirdNum, s + thirdNumStr.length());
}
}; /* code provided by PROGIEZ */
306. Additive NumberLeetCode Solution in Java
class Solution {
public boolean isAdditiveNumber(String num) {
final int n = num.length();
// num[0..i] = firstNum
for (int i = 0; i < n / 2; ++i) {
if (i > 0 && num.charAt(0) == '0')
return false;
final long firstNum = Long.parseLong(num.substring(0, i + 1));
// num[i + 1..j] = secondNum
// |thirdNum| >= max(|firstNum|, |secondNum|)
for (int j = i + 1; Math.max(i, j - i) < n - j; ++j) {
if (j > i + 1 && num.charAt(i + 1) == '0')
break;
final long secondNum = Long.parseLong(num.substring(i + 1, j + 1));
if (dfs(num, firstNum, secondNum, j + 1))
return true;
}
}
return false;
}
private boolean dfs(final String num, long firstNum, long secondNum, long s) {
if (s == num.length())
return true;
final long thirdNum = firstNum + secondNum;
final String thirdNumStr = String.valueOf(thirdNum);
return num.indexOf(thirdNumStr, (int) s) == s &&
dfs(num, secondNum, thirdNum, s + thirdNumStr.length());
}
} // code provided by PROGIEZ
306. Additive NumberLeetCode Solution in Python
class Solution:
def isAdditiveNumber(self, num: str) -> bool:
n = len(num)
def dfs(firstNum: int, secondNum: int, s: int) -> bool:
if s == len(num):
return True
thirdNum = firstNum + secondNum
thirdNumStr = str(thirdNum)
return (num.find(thirdNumStr, s) == s and
dfs(secondNum, thirdNum, s + len(thirdNumStr)))
# num[0..i] = firstNum
for i in range(n // 2):
if i > 0 and num[0] == '0':
return False
firstNum = int(num[:i + 1])
# num[i + 1..j] = secondNum
# |thirdNum| >= max(|firstNum|, |secondNum|)
j = i + 1
while max(i, j - i) < n - j:
if j > i + 1 and num[i + 1] == '0':
break
secondNum = int(num[i + 1:j + 1])
if dfs(firstNum, secondNum, j + 1):
return True
j += 1
return False # code by PROGIEZ
