#229HardDynamic Programming· Digit DP and Positional Counting

Count Unrepeated Digit Numbers

A lottery only accepts ticket numbers with **no repeated digit**: 4096 is valid, 4046 is not because the digit 4 appears twice. Ticket numbers are written in decimal without leading zeros. Given `n`, return how many integers `x` with `1 <= x <= n` have all their digits different.

Input format

`n`: the largest ticket number.

Output format

An integer: how many numbers in `[1, n]` have no repeated digit.

Examples

Input: n = 20

Output: 19

Among 1..20 only 11 repeats a digit, so 19 numbers qualify.

Input: n = 100

Output: 90

From 1 to 99 the repeated-digit numbers are 11, 22, ..., 99 (9 of them), and 100 repeats 0, so 90 numbers are valid.

Input: n = 1

Output: 1

Only the number 1 itself.

Constraints

1 <= n <= 10^9

#digit-dp
#combinatorics
#counting
#bitmask
#math