Why not check the overflow of sum?


  • 0
    H

    I was putting num1 + num2 > INT_MAX to overflow condition check but failed to pass the test case "121474836472147483648" which is suppose to split to 1 + 2147483647 = 2147483648.

    class Solution {
    public:
        bool isAdditiveNumber(string num) {
            int n = num.size();
            for (int i = 1; i <= n / 2; i++) {
                for (int j = 1; j <= n-max(i,j); j++) {
                    if (check(num, 0, i, j)) return true;
                }
            }
            return false;
        }
        
        bool check(string& s, int start, int l1, int l2) {
            if (start + l1 + l2 == s.size()) return start > 0;
            long num1 = stol(s.substr(start, l1));
            start += l1;
            long num2 = stol(s.substr(start, l2));
            if (num1 > INT_MAX || num2 > INT_MAX 
                || to_string(num1).size() != l1 || to_string(num2).size() != l2) {
                return false;
            }
            string sum1 = to_string(num1 + num2);
            string sum2 = s.substr(start + l2, sum1.size());
            return sum1 == sum2 && check(s, start, l2, sum2.size());
        }
    };
    

Log in to reply
 

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