1ms Java straightforward solution with explanation and handle with very large integers


  • 0

    Let's call num1, num2 are the first 2 number of the string number. Our task is to determine all possible pairs of the 2 numbers from the string. Let's call n is the length of the string. We have to determine how many digits in total num1 and num2 will take out of the string.

    1. To satisfy the condition, there are at least 3 numbers. The maximum digits of num1 and num2 is m = 2n/3 because the third number is the sum of the preceding two and the minimum are 2. For example, n = 9 and the maximum digits of the first 2 numbers are 6 ([3,3]) and the possible pairs will be [1,1], [1,2], [2,1], [1,3], [3,1], ...etc.

    2. Using the 2 for loops to loop through all possible pairs. At each pair, we will check the first 3 numbers satisfies the condition.If yes, we will continue check with each subsequent number until the end of the string number. Otherwise, check the next pair.

    3. For handling with very large integers, I created the function sum(char[] s1, char[] s2) to sum 2 string numbers and return the result as a string.

    public boolean isAdditiveNumber(String num) {
            int n = num.length();
            int m = 2*n/3;
            
            for (int i = 1; i < m; i++){
                for (int j = 1; j <= m - i; j++){
                    String x = num.substring(0,i);
                    String y = num.substring(i, i + j);
                    if ((x.charAt(0) == '0' && x.length() > 1) || 
                        (y.charAt(0) == '0' && y.length() > 1)) continue;
                    String value = sum(x.toCharArray(), y.toCharArray());
                    int size = value.length();
                    
                    int t = i + j + size;
                    
                    while (t <= n && value.equals(num.substring(t - size, t))){
                        if (t == n) return true;
                        x = y;
                        y = value;
                        value = sum(x.toCharArray(), y.toCharArray());
                        size = value.length();
                        t += size;
                    }
                }
            }
            
            return false;
        }
        
        private String sum(char[] s1, char[] s2){
            int n = s1.length;
            int m = s2.length;
            
            String result = "";
            
            int i = 1, remember = 0, value = 0;
            
            while (i <= n && i <= m){
                value = (s1[n-i]-48) + (s2[m - i]-48) + remember;
                remember = (value > 9)? 1: 0;
                value %= 10;
                result = value + result;
                i++;
            }
            
            while (i <= n){
                value = (s1[n-i]-48) + remember;
                remember = (value > 9)? 1: 0;
                value %= 10;
                result = value + result;
                i++;
            }
            
             while (i <= m){
                value = (s2[m-i]-48) + remember;
                remember = (value > 9)? 1: 0;
                value %= 10;
                result = value + result;
                i++;
            }
            
            result = (remember > 0)? 1 + result:result;
            
            return result;
        }
    
    

Log in to reply
 

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