Leetcode 306 Solution

This article provides solution to leetcode question 306 (additive-number)
Categories:
Tags:
Access this page by simply typing in "lcs 306" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/additive-number

Solution

class Solution {
public:
    bool isAdditiveNumber(string num) {
        for (int i = 1; i < num.size() && i < 63; i++)
        {
            string num1 = num.substr(0, i);
            int64_t inum1 = atoll(num1.c_str());

            if (inum1 != 0 && num1[0] == '0')
                continue;

            for (int j = 1; i + j < num.size() && j < 63; j++)
            {
                string num2 = num.substr(i, j);
                int64_t inum2 = atoll(num2.c_str());

                if (inum2 != 0 && num2[0] == '0')
                    continue;

                int k = i + j;

                int64_t a = inum1;
                int64_t b = inum2;

                printf("%d %d\n", i, j);
                while (k < num.size())
                {
                    int64_t c = a + b;

                    string strc = to_string(c);

                    if (num.substr(k, strc.size()) != strc)
                        break;

                    k += strc.size();
                    a = b;
                    b = c;
                }

                if (k == num.size())
                    return true;
            }
        }

        return false;
    }
};