# JAVA 0ms solution (99.5%)

• Basic Idea:

return all valid nums under upper (inclusive) - all valid nums under low (exclusive).

Suppose upper has length len. The numbers of valid nums of len_i's < len, can be very efficiently computed using recursion or Math.pow();.

For valid nums with len, construct them all and aggressively discard them if they are higher than upper (pruning). After all, char array comparison is cheap : if(compareCharArray(chs, upper, i) > 0) break;

``````public class Solution {
private static char[][] pairs = new char[][]{{'0', '0'}, {'1', '1'}, {'6', '9'}, {'8', '8'}, {'9', '6'}};
public int strobogrammaticInRange(String low, String high) {
if(low.length()>high.length() || low.length()==high.length() && high.compareTo(low)<0) return 0;
return strobogrammaticInRangeFrom0(high, true) - strobogrammaticInRangeFrom0(low, false);
}
private int strobogrammaticInRangeFrom0(String num, boolean inclusive){
int len = num.length();
if(len == 1){
if(num.charAt(0) == '0')        return inclusive ? 1 : 0;       // 0?
else if(num.charAt(0) == '1')   return inclusive ? 2 : 1;       // 0,1?
else if(num.charAt(0) < '8')    return 2;                       // 0,1
else if(num.charAt(0) == '8')   return inclusive ? 3 : 2;       // 0,1,8?
else                            return 3;                       // 0,1,8
}
int sum = 0;
for(int i = 1; i < len; i++)
sum += strobogrammaticDigit(i, true);
sum += strobogrammaticInRangeSameDigits(new char[len], 0, len - 1, num.toCharArray(),inclusive);
return sum;
}
private int strobogrammaticInRangeSameDigits(char[] chs, int i, int j, char[] upper, boolean inclusive){
int sum = 0;
if(i > j){
if( inclusive && compareCharArray(upper, chs, chs.length-1 ) >= 0 || !inclusive && compareCharArray(upper, chs, chs.length-1) > 0 )    return 1;
else    return 0;
}
for(char[] pair: pairs){
if(i == 0 && pair[0] == '0' || i==j && (pair[0] == '6' || pair[0] == '9') )     continue;
chs[i] = pair[0];
chs[j] = pair[1];
if(compareCharArray(chs, upper, i) > 0)     break;
sum += strobogrammaticInRangeSameDigits(chs, i+1, j-1, upper, inclusive);
}
return sum;
}
private int strobogrammaticDigit(int digit, boolean outside){
if(digit == 0)      return 1;
if(digit == 1)      return 3;
return outside? strobogrammaticDigit(digit-2, false)*4: strobogrammaticDigit(digit-2, false)*5;
}
private int compareCharArray(char[] arr1, char[] arr2, int idx){
for(int i = 0; i <= idx; i++)
if(arr1[i] == arr2[i])          continue;
else if(arr1[i] > arr2[i])      return 1;
else                            return -1;
return 0;
}
}``````

• great, what is the space complexity?

• Same 0ms, time O(logN), space O(1), N is the output, non-recursive.

``````static final int[] FIVE = {0, 1, 6, 8, 9};
static final int[] THREE = {0, 1, 8};
public int strobogrammaticInRange(String low, String high) {
int ans = 0, m = low.length(), n = high.length();
if (m > n || m == n && low.compareTo(high) > 0) return 0;
ans = helper(m, low, true);
for (int i = m + 1; i <= n; ++i) {
ans += helper(i, null, true);
}
return ans - helper(n, high, false);
}
int helper(int n, String lo, boolean inclusive) {
int ans = 0;
boolean same = true;
for (int i = 0; i < n/2; ++i) {
ans *= 5;
if (!same) continue;
ans += lo == null ? 4 : count(i, lo, FIVE);
if (lo == null || lo.charAt(i) > '1' && lo.charAt(i) < '8' && lo.charAt(i) != '6') same = false;
}
if (n % 2 == 1) {
ans *= 3;
if (same) {
ans += count(n/2, lo, THREE); // lo is not null. n > 1, not same; n = 1, it's low.
if (lo.charAt(n/2) > '1' && lo.charAt(n/2) != '8') same = false;
}
}
if (same) {
String s = get(lo);
if (s.compareTo(lo) > 0 || inclusive && s.equals(lo)) ans++;
}
return ans;
}
int count(int i, String lo, int[] arr) {
int cnt = 0, lower = lo.charAt(i) - '0';
for (int d : arr) {
if (d > lower) cnt++;
}
return cnt;
}
String get(String str) {
int n = str.length();
StringBuilder sb = new StringBuilder(str.substring(0, (n + 1)/2));
for (int i = n/2 - 1; i >= 0; --i) {
if (str.charAt(i) == '6') sb.append('9');
else if (str.charAt(i) == '9') sb.append('6');
else sb.append(str.charAt(i));
}
return sb.toString();
}
``````

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