> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/math/strobogrammatic-number-iii.md).

# Strobogrammatic Number III

> A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).
>
> Return the number of all strobogrammatic numbers that are of length from 1 to n.
>
> For example,\
> Given n = 2, return 7, because `["0", "1", "8", "11","69","88","96"]`.

## Thoughts

排列问题. 对于长度为n的, 如果是偶数, 那么左半边可以为\[0, 1, 8, 6, 9]四个数的任意组合, 但0不能排在左半边的最外面的, 因此除最外层有5 ^ (n / 2 - 1) 排列方式, 再乘以除0外剩余4个. 奇数的话在此基础上\*3, 因为能取\[0 , 1, 8].

## Code

```
int res = 1;
        for (int i = 1; i <= n; i++) {
            int tmp = 4 * Math.pow(5, n / 2 - 1);
            if (n % 2 == 1) {
                tmp *= 3;
            }
            res += tmp;
        }
        return res;
```

## Analysis

时间复杂度O(N).