### How many reversible numbers are there below one-billion?题号：145 难度： 20 中英对照

Some positive integers n have the property that the sum [ n + reverse(n) ] consists entirely of odd (decimal) digits. For instance, 36 + 63 = 99 and 409 + 904 = 1313. We will call such numbers reversible; so 36, 63, 409, and 904 are reversible. Leading zeroes are not allowed in either n or reverse(n).

There are 120 reversible numbers below one-thousand.

How many reversible numbers are there below one-billion (109)?

### Code

public  class p145  {

public static void main(String[] args) {
long start=System.nanoTime();
String result = run();
long end=System.nanoTime();
System.out.println(result);
System.out.println( (end-start)/1000000 + "ms" );
}

public static String run() {
int sum = 0;
for (int digits = 1; digits <= 9; digits++) {
if (digits % 2 == 0)
sum += 20 * pow(30, digits / 2 - 1);
else if (digits % 4 == 3)
sum += 100 * pow(500, (digits - 3) / 4);
else if (digits % 4 == 1)
sum += 0;
else
throw new AssertionError();
}
return Integer.toString(sum);
}

// Returns x to the power of y, throwing an exception if the result overflows an int.
public static int pow(int x, int y) {
if (x < 0)
throw new IllegalArgumentException("Negative base not supported");
if (y < 0)
throw new IllegalArgumentException("Negative exponent");
int z = 1;
for (int i = 0; i < y; i++) {
if (Integer.MAX_VALUE / z < x)
throw new ArithmeticException("Overflow");
z *= x;
}
return z;
}
}
608720
1ms