C++ very large integer solution, based on string arithmetics


  • 0
    A

    All numbers are represented by string intead of int, so basically there is no limit how large the number can be.
    I don't like recursive function, but sometimes we don't have a choice.

    37 / 37 test cases passed
    Status: Accepted
    Runtime: 0 ms

    class Solution {
    public:
        bool bt(string& str, uint pos, string& a, string& b) {
            uint siz = str.size();
            if (pos == siz) return true;
            string sum;
            for (int carry = 0, i = a.size()-1, j = b.size()-1; carry || i >= 0 || j >= 0; i--, j--) {
                carry += (i >= 0 ? a[i]-'0' : 0) + (j >= 0 ? b[j]-'0' : 0);
                sum.push_back(carry % 10 + '0');
                carry /= 10;
            }
            int k = sum.size()-1;
            for ( ; k >= 0 && pos < siz; k--, pos++) {
                if (str[pos] != sum[k]) break;
            }
            if (k < 0) {
                reverse(sum.begin(), sum.end());
                if (bt(str, pos, b, sum)) return true;
            }
            return false;
        }
        
        bool isAdditiveNumber(string num) {
            uint siz = num.size();
            if (!siz) return true;
            if (siz < 3) return false;
            string a, b;
            for (uint i = 0, e = siz-2; i < e; i++, e--) {
                if (!a.empty() && a[0] == '0') break;
                a.push_back(num[i]);
                b.clear();
                for (uint j = i+1, ee = e+1; j < ee; j++, ee = j - i > i + 1 ? ee-- : ee) {
                    if (!b.empty() && b[0] == '0') break;
                    b.push_back(num[j]);
                    if (bt(num, j+1, a, b)) return true;
                }
            }
            return false;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.