# 1 ms Java solution with explanation and comments

• This idea is as following:

1. split solution to three parts:
for numbers with low.length digits, how many strobogrammatic numbers>= low
for numbers with hi.length digits, how many strobogrammatic numbers<= hi
for numbers with digits n that lo<n<hi, count the f(n)

1. for n-digit number, how many strobogrammatic number exist:
n count
0 0
1 3
2 4
3 3* 4=12
4 4* 5=20
5 12* 5=60
6 20* 5=100

so f(n) = 0 when n=0
=3 when n=1
=4 when n=2
=12 when n=3
= f(n-2) / 4 * 5* 4 = 5*f(n-2) when n>3

1. core part is count the stro numbers <= hi, with the hi.length digits.
``````public class StrobogrammaticNumberIII {

private char[] compArr = { '0', '1', '6', '8', '9' };
private char[] symArr = { '0', '1', '9', '8', '6' };
private char[] oneDigitArr = { '0', '1', '8' };
public int strobogrammaticInRange(String low, String high) {

// validation
if (low == null || high == null || low.length() == 0 || high.length() == 0
|| low.length() > high.length()) {
return 0;
}

int count = 0;
char[] l = low.toCharArray();
char[] h = high.toCharArray();

if (l.length == h.length) {
// count of stro numbers that <=hi
int a = countLess(h, 0, h.length);
// count of stro numbers that <lo
int b = countLess(l, 0, l.length);
if (isStroNum(l)) {
b--;
}

return a - b;
}
// count of stro number>=lo in all lo.length-digit numbers
count += countNdigit(l.length) - countLess(l, 0, l.length);
if (isStroNum(l)) {
count++;
}
// count of stro numbers<=hi
count += countLess(h, 0, h.length);

for (int i = l.length + 1; i < h.length; i++) {
count += countNdigit(i);
}

return count < 0 ? 0 : count;
}

private boolean isStroNum(char[] c) {

for (int i = 0; i <= c.length / 2; i++) {
if (c[i] == '0' || c[i] == '1' || c[i] == '8') {
if (c[c.length - 1 - i] != c[i]) {
return false;
}
}
if (c[i] == '6') {
if (c[c.length - 1 - i] != '9') {
return false;
}
}
if (c[i] == '9') {
if (c[c.length - 1 - i] != '6') {
return false;
}
}

}

return true;

}

// how many strobogrammatic numbers with n-digits
private int countNdigit(int n) {
if (n <= 0) {
return 0;
}
if (n == 1) {
return 3;
}
if (n == 2) {
return 4;
}
if (n == 3) {
return 12;
}

return countNdigit(n - 2) * 5;
}

/**
* count how many strobogrammatic numbers equals or less than s in all numbers with c.length
* digits count from left to right, if the digit>compArr[k], then count+=countLess(c, index+1,
* n-2) Attention: handle the edge condition such as the most outer layer, n==1, n==2,etc.
*
* @param c
*            char[]
* @param index
*            starts from 0,add 2 each step
* @param n
*            the length of char array c
* @return count of strobogrammatic numbers
*/
private int countLess(char[] c, int index, int n) {
int count = 0;
boolean flag;

if (n > 0) {
int k = 0;
// only compare 0,1,8
if (n == 1) {
for (; k < oneDigitArr.length; k++) {
if (c[index] >= oneDigitArr[k]) {
count++;
}
}
return count;
}
// for the outer most layer, do not count{0,0}
if (n == c.length) {
k++;
}
for (; k < compArr.length; k++) {
if (c[index] > compArr[k]) {
count += innerCount(n);
} else if (c[index] == compArr[k]) {

// check the symmetric position
flag = c[c.length - 1 - index] >= symArr[k];
if (n <= 2) {
if (flag) {
count++;
}
} else {
count += countLess(c, index + 1, n - 2);
char[] innerArr = new char[c.length - 2 * (index + 1)];
System.arraycopy(c, index + 1, innerArr, 0, innerArr.length);
// when the inner layer is exactly a stro number and the out layer is not
// symmetric, count--
if (!flag && isStroNum(innerArr)) {
count--;
}
}
return count;
} else {
return count;
}

}
}

return count;
}

// helper method to count the numbers when c[index]>compArr[k]
private int innerCount(int n) {

if (n == 1 || n == 2) {
return 1;
}
if (n == 3) {
return countNdigit(n - 2);
}

return countNdigit(n - 2) / 4 * 5;

}

}
``````

Hope that helps :)

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