package leetcode;

/**
 * https://leetcode.com/problems/additive-number/
 */
public class Problem306 {
    public boolean isAdditiveNumber(String num) {
        for (int i = 0; i < num.length(); i++) {
            boolean result = isAdditiveNumber(num, i + 1);
            if (result) {
                return true;
            }
        }
        return false;
    }

    private boolean isAdditiveNumber(String num, int idx) {
        long a = Long.parseLong(num.substring(0, idx));
        int beg = idx;
        for (int i = 1; i < num.length(); i++) {
            int endIdx = idx + i;
            while (endIdx <= num.length()) {
                long b = Long.parseLong(num.substring(beg, endIdx));
//                System.out.println("a=" + a + ", b=" + b + ", end=" + end);
                boolean result = isAdditiveNumber(num, a, b, endIdx);
                if (result) {
                    return true;
                }
                break;
            }
        }
        return false;
    }

    private boolean isAdditiveNumber(String num, long a, long b, int idx) {
//        System.out.println("trying: a=" + a + ", b=" + b + ", idx=" + idx);
        long x = a;
        long y = b;
        long sum = x + y;
        String sumStr = Long.toString(sum);
        int begIdx = idx;
        int endIdx = begIdx + sumStr.length();
        if (endIdx > num.length()) {
            return false;
        }
        String nextStr = num.substring(begIdx, endIdx);
        if (!sumStr.equals(nextStr)) {
            return false;
        }
        while (endIdx < num.length()) {
            x = y;
            y = sum;
            sum = x + y;
            begIdx = endIdx;
            endIdx = begIdx + sumStr.length();
            if (endIdx > num.length()) {
                return false;
            }
            sumStr = Long.toString(sum);
            nextStr = num.substring(begIdx, endIdx);
            if (!sumStr.equals(nextStr)) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Problem306 prob = new Problem306();
        // 1 1 2 3 5 8
//        System.out.println(prob.isAdditiveNumber("112358")); // true
//        System.out.println(prob.isAdditiveNumber("112358", 1, 1, 2));
        // 1 99 100 199
//        System.out.println(prob.isAdditiveNumber("199100199")); // true
//        System.out.println(prob.isAdditiveNumber("199100199", 1, 99, 3)); // true
        // 11 3 14 17 31
//        System.out.println(prob.isAdditiveNumber("113141731")); // true
//        System.out.println(prob.isAdditiveNumber("113141731", 11, 3, 3)); // true
        // 113 14 127 141
//        System.out.println(prob.isAdditiveNumber("11314127141")); // true
//        System.out.println(prob.isAdditiveNumber("11314127141", 113, 14, 5)); // true
        // 1980 1982 3962
//        System.out.println(prob.isAdditiveNumber("198019823962")); // true
    }
}

@@ -12,16 +12,46 @@
 tcode;%0A%0A
+import java.math.BigInteger;%0A%0A
 /**%0A * h
@@ -464,31 +464,37 @@
     
-long a = Long.parseLong
+BigInteger a = new BigInteger
 (num
@@ -624,37 +624,34 @@
  i;%0A            
-while
+if
  (endIdx %3C= num.
@@ -682,32 +682,21 @@
     
-long b = Long.parseLong(
+String str = 
 num.
@@ -721,13 +721,10 @@
 Idx)
-)
 ;%0A
-//
     
@@ -739,65 +739,156 @@
     
-System.out.println(%22a=%22 + a + %22, b=%22 + b + %22, end=%22 + end
+if (str.length() %3E 1 && str.startsWith(%220%22)) %7B%0A                    return false;%0A                %7D%0A                BigInteger b = new BigInteger(str
 );%0A 
@@ -1041,31 +1041,8 @@
   %7D%0A
-                break;%0A
     
@@ -1143,20 +1143,32 @@
 um, 
-long a, long
+BigInteger a, BigInteger
  b, 
@@ -1178,26 +1178,24 @@
  idx) %7B%0A
-//
         
 System.o
@@ -1190,88 +1190,18 @@
     
-System.out.println(%22trying: a=%22 + a + %22, b=%22 + b + %22, idx=%22 + idx);%0A        long
+BigInteger
  x =
@@ -1212,20 +1212,26 @@
         
-long
+BigInteger
  y = b;%0A
@@ -1242,20 +1242,26 @@
     
-long
+BigInteger
  sum = x
  + y
@@ -1248,36 +1248,39 @@
 gInteger sum = x
- + y
+.add(y)
 ;%0A        String
@@ -1281,36 +1281,35 @@
 String sumStr = 
-Long
+sum
 .toString(sum);%0A
@@ -1294,35 +1294,32 @@
  = sum.toString(
-sum
 );%0A        int b
@@ -1685,12 +1685,52 @@
  = x
- + y
+.add(y);%0A            sumStr = sum.toString()
 ;%0A  
@@ -1892,49 +1892,8 @@
   %7D%0A
-            sumStr = Long.toString(sum);%0A
     
@@ -2030,32 +2030,32 @@
     %7D%0A        %7D%0A
+
         return t
@@ -2068,927 +2068,7 @@
    %7D
-%0A%0A    public static void main(String%5B%5D args) %7B%0A        Problem306 prob = new Problem306();%0A        // 1 1 2 3 5 8%0A//        System.out.println(prob.isAdditiveNumber(%22112358%22)); // true%0A//        System.out.println(prob.isAdditiveNumber(%22112358%22, 1, 1, 2));%0A        // 1 99 100 199%0A//        System.out.println(prob.isAdditiveNumber(%22199100199%22)); // true%0A//        System.out.println(prob.isAdditiveNumber(%22199100199%22, 1, 99, 3)); // true%0A        // 11 3 14 17 31%0A//        System.out.println(prob.isAdditiveNumber(%22113141731%22)); // true%0A//        System.out.println(prob.isAdditiveNumber(%22113141731%22, 11, 3, 3)); // true%0A        // 113 14 127 141%0A//        System.out.println(prob.isAdditiveNumber(%2211314127141%22)); // true%0A//        System.out.println(prob.isAdditiveNumber(%2211314127141%22, 113, 14, 5)); // true%0A        // 1980 1982 3962%0A//        System.out.println(prob.isAdditiveNumber(%22198019823962%22)); // true%0A    %7D
 %0A%7D%0A

Solve problem 306