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;
    }
};