*Java* very straightforward solution with detailed explanation


  • 49
    E

    The idea is quite straightforward:

    1. Choose the first number A, it can be the leftmost 1 up to i digits. i<=(L-1)/2 because the third number should be at least as long as the first number

    2. Choose the second number B, it can be the leftmost 1 up to j digits excluding the first number. the limit for j is a little bit tricky, because we don't know whether A or B is longer. The remaining string (with length L-j) after excluding A and B should have a length of at least max(length A, length B), where length A = i and length B = j-i, thus L-j >= max(j-i, i)

    3. Calls the recursive checker function and returns true if passes the checker function, or continue to the next choice of B (A) until there is no more choice for B or A, in which case returns a false.

    Here is the code in Java:

        public boolean isAdditiveNumber(String num) {
            int L = num.length();
    
            // choose the first number A
            for(int i=1; i<=(L-1)/2; i++) {
                // A cannot start with a 0 if its length is more than 1
                if(num.charAt(0) == '0' && i>=2) break; //previous code: continue;
            
                // choose the second number B
                for(int j=i+1; L-j>=j-i && L-j>=i; j++) {
                    // B cannot start with a 0 if its length is more than 1
                    if(num.charAt(i) == '0' && j-i>=2) break; // previous: continue;
                
                    long num1 = Long.parseLong(num.substring(0, i)); // A
                    long num2 = Long.parseLong(num.substring(i, j)); // B
                    String substr = num.substring(j); // remaining string
                
                    if(isAdditive(substr, num1, num2)) return true; // return true if passes isAdditive test
                    // else continue; // continue for loop if does not pass isAdditive test
                }
            }
            return false; // does not pass isAdditive test, thus is not additive
        }
    
        // Recursively checks if a string is additive
        public boolean isAdditive(String str, long num1, long num2) {
            if(str.equals("")) return true; // reaches the end of string means a yes
        
            long sum = num1+num2;
            String s = ((Long)sum).toString();
            if(!str.startsWith(s)) return false; // if string does not start with sum of num1 and num2, returns false
        
            return isAdditive(str.substring(s.length()), num2, sum); // recursively checks the remaining string
        }
    

    If you are interested in my other posts, please feel free to check my Github page here: https://github.com/F-L-A-G/Algorithms-in-Java


  • 0
    L

    The "else continue;" part in the inner loop can be removed safely.


  • 0
    E

    Yes, you are right.


  • 0
    B

    What is the time complexity?


  • 0
    B

    It should be discussed whether "11" "1" is additive.


  • 0
    E

    @XiaoboZhang1991, there is no need to think about 11 or 1 because the problem states the following:

    A valid additive sequence should contain at least three numbers.
    

    As of the time complexity, since we have two for loops, the time complexity should be O(n^2) where n is the length of the number.


  • 0
    Y

    in this statement " if (num.charAt(0) == '0' && i >= 2) continue;", why is it "continue", but not "break"?


  • 0
    S

    I agree with you. We can simply break and save a little computation
    Once num.charAt(0) == '0', the only possible first number is 0, no need to check 0x 0xx 0xxx
    Same goes with the next continue


  • 0
    E

    @yanlantao, @stupidbird911, both of you are right. We can safely break if we notice it starts with a 0 and its length is larger than 1.


  • -1
    S

    Is there any thought of solving the follow up "How would you handle overflow for very large input integers?"


  • 0
    X

    I believe that this code can handle the large case input, right?

    class Solution {
    public:
        bool isAdditiveNumber(string num) {
            if (num.length() < 3) return false;
            int len = num.length();
            // first chhose A, A <= (len - 1) / 2
            for (int i = 1; i <= (len - 1) / 2; i++) {
                if (num[0] == '0' && i >= 2) break; // break this loop when the first digit is zero
                string A = num.substr(0, i);
                // second choose B
                for (int j = 1; ; j++) {
                    if (len - (i + j) < max(i, j)) break;
                    if (num[i] == '0' && j >= 2) break;
                    string B = num.substr(i, j);
                    if ( isAdditive( num.substr(i + j), A, B ) ) return true;
                }
            }
            return false;
        }
        
        bool isAdditive(string str, string A, string B) {
            if (str == "") return true;
            string des = addDigit(A, B);
            if ( ! ( str.find( des ) == 0 ) ) return false;
            return isAdditive(str.substr(des.length()), B, des);
        }
        
        string addDigit(string A, string B) {
            int pA = A.length() - 1;
            int pB = B.length() - 1;
            string des = "";
            int carry = 0;
            while (pA >= 0 && pB >= 0) {
                int tmp = (A[pA] - '0') + (B[pB] - '0') + carry;
                des = (char)('0' + tmp % 10) + des;
                carry = tmp / 10;
                pA--;
                pB--;
            }
            while (pA >= 0) {
                int tmp = (A[pA] - '0') + carry;
                des = (char)('0' + tmp % 10) + des;
                carry = tmp / 10;
                pA--;
            }
            while (pB >= 0) {
                int tmp = (B[pB] - '0') + carry;
                des = (char)('0' + tmp % 10) + des;
                carry = tmp / 10;
                pB--;
            }
            if (carry)
                des = '1' + des;
            return des;
        }
    };

  • 0
    W

    Great solution. Just translate it to Python:

    class Solution(object):
        def isAdditiveNumber(self, num):
            """
            :type num: str
            :rtype: bool
            """
            # Idea: find the first 2 strings and then continue to check the remaining strings
            L = len(num)
            # 1st number is num[0:i], 2nd number is num[i:j]
            for i in range(1, L/2+1):
                if num[0] == '0' and i >= 2: break   
                for j in range(i+1, min(L-i, (L+i)/2)+1):
                    if num[i] == '0' and j-i >= 2: break     # means starting with "0", e.g., "03"
                    num1 = num[0:i]
                    num2 = num[i:j]
                    remain = num[j:]
                    if self.isAdditive(num1, num2, remain):
                        return True
                        
            return False
            
                    
        def isAdditive(self, num1, num2, remain):
            if remain == "":    # means checked whole string
                return True
            total = str( int(num1) + int(num2) )
            if remain.startswith(total):
                return self.isAdditive(num2, total, remain[len(total):])
            else:
                return False  
                
    

  • 0
    B

    why allow so much slack room for the leading 0? if you only check that you're using a number with a leading 0 when i >= 2, then you've already absorbed more than 1 digit, and that causes problems

    it should be i>=1 no?


  • 0
    C

    great solution, easy to understand, thx


  • 0
    T

    shouldnt complexity of this solution be 0(N3) ?


  • 0
    C

    thanks for sharing, your solution is really smart.


Log in to reply
 

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