Distinct digit count
algorithm, count, digit, distinct
Solution
I assume `N` is the number of digits of `n`. If the size of `n` is unlimited, it can't be done in general in O(1) time.
Consider the number `n=11111...111`, with 2 trillion digits. If I switch one of the digits from a `1` to a `2`, there is no way to discover this without in some way looking at every single digit. Thus processing a number with 2 trillion digits must take (of the order of) 2 trillion operations at least, and in general, a number with `N` digits must take (of the order of) `N` operations at least.
However, for almost all numbers, the simple `O(N)` algorithm finishes very quickly because you can just stop as soon as you get to 10 distinct digits. Almost all numbers of sufficient length will have all 10 digits: e.g. the probability of not terminating with the answer '10' after looking at the first 100 digits is about 0.00027, and after the first 1000 digits it's about 1.7e-45. But unfortunately, there are some oddities which make the worst case `O(N)`.
Problem
Is is possible to count the distinct digits in a number in constant time `O(1)`? Suppose `n=1519` output should be `3` as there are `3` distinct digits`(1,5,9)`. I have done it in `O(N)` time but anyone knows how to find it in `O(1)` time?