algoadvance

Leetcode 306. Additive Number

Problem Statement:

A positive integer is called an additive number if it is a sequence of numbers such that the sum of any two consecutive numbers is equal to the next number.

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, except for the number 0 itself.

Clarifying Questions:

  1. Can the input string contain non-digit characters?
    • No, the string will contain only digits as per the problem statement.
  2. What is the minimum length of the input string?
    • The minimum length for an input string to possibly be an additive number is 3.
  3. What should be done if the string length is less than 3?
    • We should immediately return false because a valid additive number sequence requires at least three numbers.
  4. How should we handle large numbers that might cause overflow in typical integer storage?
    • Since the problem deals with potentially very large numbers generated by string operations, using large integer handling provided by languages (like strings in C++) will be handy.

Strategy:

  1. Iterate over all possible starting pairs (num1, num2) within the input string.
  2. For each pair, attempt to build the sequence by repeatedly checking if the sum of the pair equals the next segment in the string.
  3. Ensure no leading zeros in num1 and num2 unless they are 0 themselves.
  4. If we can build the sequence up to the end of the input string, return true.
  5. If no valid sequence can be created, return false.

Code:

#include <string>
#include <iostream>
using namespace std;

class Solution {
public:
    bool isAdditiveNumber(string num) {
        int n = num.size();
        // Try every possible first and second number
        for (int i = 1; i <= n / 2; ++i) {
            for (int j = 1; max(i, j) <= n - i - j; ++j) {
                if (isValid(num.substr(0, i), num.substr(i, j), num.substr(i + j))) {
                    return true;
                }
            }
        }
        return false;
    }

    bool isValid(string num1, string num2, string remaining) {
        if ((num1.size() > 1 && num1[0] == '0') || (num2.size() > 1 && num2[0] == '0')) {
            return false;
        }
        string sum = addStrings(num1, num2);
        if (remaining == sum) {
            return true;
        }
        if (remaining.size() < sum.size() || remaining.substr(0, sum.size()) != sum) {
            return false;
        }
        return isValid(num2, sum, remaining.substr(sum.size()));
    }

    string addStrings(string num1, string num2) {
        int carry = 0, n1 = num1.size(), n2 = num2.size(), i = n1 - 1, j = n2 - 1;
        string result;
        while (i >= 0 || j >= 0 || carry) {
            int x = (i >= 0) ? num1[i--] - '0' : 0;
            int y = (j >= 0) ? num2[j--] - '0' : 0;
            int sum = x + y + carry;
            result.push_back(sum % 10 + '0');
            carry = sum / 10;
        }
        reverse(result.begin(), result.end());
        return result;
    }
};

int main() {
    Solution sol;
    string num = "112358";
    cout << (sol.isAdditiveNumber(num) ? "True" : "False") << endl;  // Output: True
    
    num = "199100199";
    cout << (sol.isAdditiveNumber(num) ? "True" : "False") << endl;  // Output: True
    
    num = "123";
    cout << (sol.isAdditiveNumber(num) ? "True" : "False") << endl;  // Output: True
    
    num = "1203";
    cout << (sol.isAdditiveNumber(num) ? "True" : "False") << endl;  // Output: False
    
    return 0;
}

Time Complexity:

Space Complexity:

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI