Distinct Digits
InterviewTime limit1sMemory limit1024 MB
Count the integers in [A, B], where B can be up to 10^100, whose decimal digits are all distinct and have no leading zeros.
- Level
Medium5 of 10
- Topics
- Dynamic programming, Bit manipulation, String
- Solved
- No attempts yet
Problem
One of the interesting facts about Eli is that she watches television. In fact, she follows shows that look pointless at first glance, like "Ало, Къщата". The real reason is one of the charming hosts, Kosyo. The show asks a series of easy questions (easy even for Eli), and people are happy to answer them and then call in, which makes the producers, and therefore the hosts, richer (and even more attractive to Eleonora).
One of the riddles goes like this: what do the numbers 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768 have in common? Most viewers would say these are the first powers of two. Others would suggest a geometric progression with ratio 2, and a third group would come up with something else. In fact, a sequence like this has many valid answers, and the hosts can pick which one is the "correct" one only at the end of the show, so that none of the callers wins.
For example, one possible answer is that this is a sequence of numbers in which no digit repeats. Indeed, in each of the numbers above, every digit appears at most once in the decimal representation. After hearing this unexpected answer, Eli wonders how many such numbers there actually are. The next few powers of two are not of this kind (65536, 131072, 262144, 524288), but 1048576 is again, while 2097152 and 4194304 are not. Overall, these numbers are fairly unpredictable (up to a point \u263a).
Eli gives you the following modified problem. For a given interval , count how many integers in the interval have no repeated digit in their decimal representation. The numbers must also have no leading zeros. Write a program named unique that solves this problem.
Input
The first and only line of standard input contains the integers A and B.
Output
Print to standard output a single integer, the answer to the problem.
Constraints
Hint
Explanation: In the first example, the numbers that do not satisfy the condition are 11, 22, 33, 44, 55, 66, 77, 88, 99, and 100.