# Java 0ms non-recursive solution with explanation

• Normal solutions traverse the string from left to right, but mine does this reversely. It brings two obvious benefits: 1. easy to determine the range of sum (1 to len/2) and the range of one addend (1 to sum.length); 2. easy to locate the suffix of the other addend, so that we can directly compare the three corresponding digits.

The string is partitioned like this:

0..............a (j)...........b (i).....c (len)

|_............._|_addend_|_sum_|

Below is my code:

``````   public boolean isAdditiveNumber(String num) {
if(num == null)
return false;
int len = num.length(), len1 = len - 1;
if(len < 3)
return false;
char[] carray = num.toCharArray();
int bound = (len + 1) / 2, bound2, a, b, c = len, idx;
for(int i = len1;i >= bound;i--){
if(i < len1 && carray[i] == '0') //leading zero
continue;
b = i;
bound2 = 2 * i - len; //len - i >= i - j
for(int j = i-1;j >= bound2;j--){
if(j < i - 1 && carray[j] == '0') //leading zero
continue;
a = j;
while((idx = getSuffix(carray, a, b, c)) >= 0){
if(idx == 0)
return true;
c = b;
b = a;
a = idx;
}
b = i;
c = len;
}
}
return false;
}

private int getSuffix(char[] num, int a, int b, int c){
//    	System.out.println(String.valueOf(num, 0, a) + " " + String.valueOf(num, a, b-a) + " " + String.valueOf(num, b, c-b));
boolean borrow = false, leadingZero = false;
int i = a - 1, j = b - 1, k = c - 1, x, y, z, zeros = 0;
while(k >= b){
z = num[k--] - '0';
if(borrow)
z--;
y = j >= a ? num[j--] - '0' : 0;
if(z < y){
borrow = true;
z += 10;
}
else
borrow = false;
if(y != z){
if(leadingZero && zeros > 0){
while(i >= 0 && zeros > 0){
if(num[i--] != '0')
return -1;
zeros--;
}
if(zeros > 0)
return -1;
}
if(i < 0)
return -1;
x = num[i--] - '0';
if(x + y != z)
return -1;
leadingZero = false;
zeros = 0;
}
else if(leadingZero)
zeros++;
else{
if(i == a - 1){
if(num[i--] != '0')
return -1;
leadingZero = true;
}
else{
leadingZero = true;
zeros++;
}
}
}

return i + 1;
}``````

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