Numbers That Read the Same Upside Down

Interview

Time limit1sMemory limit128 MB

Summary

Count how many integers in the interval [m, n] stay the same when rotated 180 degrees, using the digit map 0, 1, 8, 6, 9.

Level: Easy3 of 10
Topics: Math, Implementation, Brute force, String matching
Solved: No attempts yet

Problem

The digits $0$ , $1$ , and $8$ look almost the same when the page is rotated $180$ degrees (turned upside down). The digit $6$ looks like a $9$ when rotated this way, and $9$ looks like a $6$ .

A multi-digit number can also look like itself when the page is turned upside down. For example, $9966$ and $10\,801$ do, but $999$ and $1234$ do not.

Write a program that counts how many numbers in a given interval look the same after being rotated $180$ degrees. For example, the interval $[1 \dots 100]$ contains six such numbers: $1$ , $8$ , $11$ , $69$ , $88$ , and $96$ .

Input. Two integers $m$ and $n$ that define the interval to check ( $1 \le m \le n \le 32\,000$ ). You may assume the input is always valid.

Output. Print how many numbers in $[m, n]$ look the same when rotated $180$ degrees.

Examples5

Example 1
Input
```
1
100
```
Expected output
```
6
```
Example 2
Input
```
1
9
```
Expected output
```
2
```
Example 3
Input
```
1
10
```
Expected output
```
2
```
Example 4
Input
```
69
96
```
Expected output
```
3
```
Example 5
Input
```
100
1000
```
Expected output
```
12
```