Count all numbers with unique digits in a given range

Question

This is an interview question. Count all numbers with unique digits (in decimal) in the range [1, N].

The obvious solution is to test each number in the range if its digits are unique. We can also generate all numbers with unique digits (as permutations) and test if they are in the range.

Now I wonder if there is a DP (dynamic programming) solution for this problem.

Answer 1

I'm thinking:

Number of unique digits numbers 1-5324
=   Number of unique digits numbers 1-9
  + Number of unique digits numbers 10-99
  + Number of unique digits numbers 100-999
  + Number of unique digits numbers 1000-5324

So:

f(n) = Number of unique digits numbers with length n.
f(1) = 9 (1-9)
f(2) = 9*9 (1-9 * 0-9 (excluding first digit))
f(3) = 9*9*8 (1-9 * 0-9 (excluding first digit) * 0-9 (excluding first 2 digits))
f(4) = 9*9*8*7

Add all of the above until you get to the number of digits that N has minus 1.

Then you only have to do Number of unique digits numbers 1000-5324

And:

Number of unique digits numbers 1000-5324
=   Number of unique digits numbers 1000-4999
  + Number of unique digits numbers 5000-5299
  + Number of unique digits numbers 5300-5319
  + Number of unique digits numbers 5320-5324

So:

N = 5324

If N[0] = 1, there are 9*8*7 possibilities for the other digits
If N[0] = 2, there are 9*8*7 possibilities for the other digits
If N[0] = 3, there are 9*8*7 possibilities for the other digits
If N[0] = 4, there are 9*8*7 possibilities for the other digits
If N[0] = 5
  If N[1] = 0, there are 8*7 possibilities for the other digits
  If N[1] = 1, there are 8*7 possibilities for the other digits
  If N[1] = 2, there are 8*7 possibilities for the other digits
  If N[1] = 3
    If N[2] = 0, there are 7 possibilities for the other digits
    If N[2] = 1, there are 7 possibilities for the other digits
    If N[2] = 2
      If N[3] = 0, there is 1 possibility (no other digits)
      If N[3] = 1, there is 1 possibility (no other digits)
      If N[3] = 2, there is 1 possibility (no other digits)
      If N[3] = 3, there is 1 possibility (no other digits)

The above is something like:

uniques += (N[0]-1)*9!/(9-N.length+1)!
for (int i = 1:N.length)
  uniques += N[i]*(9-i)!/(9-N.length+1)!

// don't forget N
if (hasUniqueDigits(N))
  uniques += 1

You don't really need DP as the above should be fast enough.

EDIT:

The above actually needs to be a little more complicated (N[2] = 2 and N[3] = 2 above is not valid). It needs to be more like:

binary used[10]
uniques += (N[0]-1)*9!/(9-N.length+1)!
used[N[0]] = 1
for (int i = 1:N.length)
  uniques += (N[i]-sum(used 0 to N[i]))*(9-i)!/(9-N.length+1)!
  if (used[N[i]] == 1)
    break
  used[N[i]] = 1

// still need to remember N
if (hasUniqueDigits(N))
  uniques += 1

Answer 2

a python solution is summarized as follow ：

the solution is based on the mathematical principle of Bernhard Barker provided previous in the answer list:

thanks to Bernhard's ideal

def count_num_with_DupDigits(self, n: int) -> int:
    # Fill in your code for the function. Do not change the function name
    # The function should return an integer.
    n_str = str(n)
    n_len = len(n_str)
    n_unique = 0
    
    
    # get the all the x000 unique digits
    if n > 10:
        for i in range(n_len-1):
            n_unique = n_unique + 9*int(np.math.factorial(9)/np.math.factorial(10-n_len+i+1))
        m=0
        if m == 0:
            n_first  = (int(n_str[m])-1)*int(np.math.factorial(9)/np.math.factorial(10-n_len))
        m=m+1
        count_last=0
        n_sec=0
        
        
        for k in range(n_len-1):
            if m == n_len-1:
                count_last = int(n_str[m])+1
                for l in range(int(n_str[m])+1):a
                           if n_str[0:n_len-1].count(str(l)) > 0:
                               count_last = count_last-1
              
            else:
                for s in range(int(n_str[k+1])):
                    if n_str[0:k+1].count(str(s))>0:
                        n_sec=n_sec
                    else:
                        n_sec = int(np.math.factorial(9-m)/np.math.factorial(10-n_len))+n_sec
                if n_str[0:k+1].count(n_str[k+1]) > 0:
                    break
                m= m+1

        value=n-(n_sec+n_first+n_unique+count_last)
    else:
        value = 0
    return value

Answer 3

For an interview question like this, a brute-force algorithm is probably intended, to demonstrate logic and programming competency. But also important is demonstrating knowledge of a good tool for the job.

Sure, after lots of time spent on the calculation, you can come up with a convoluted mathematical formula to shorten a looping algorithm. But this question is a straightforward example of pattern-matching, so why not use the pattern-matching tool built in to just about any language you'll be using: regular expressions?

Here's an extremely simple solution in C# as an example:

string csv = string.Join(",", Enumerable.Range(1, N));
int numUnique = N - Regex.Matches(csv, @"(\d)\d*\1").Count;

Line 1 will differ depending on the language you use, but it's just creating a CSV of all the integers from 1 to N.

But Line 2 would be very similar no matter what language: count how many times the pattern matches in the csv.

The regex pattern matches a digit possibly followed by some other digits, followed by a duplicate of the first digit.

Answer 4

Lazy man's DP:

Prelude> :m +Data.List
Data.List> length [a | a <- [1..5324], length (show a) == length (nub $ show a)]
2939

Answer 5

Although this question had been posted in 2013, I feel like it is still worthy to provide an implementation for reference as other than the algorithm given by Dukeling I couldn't find any implementation on the internet.

I wrote the code in Java for both brute force and Dukeling's permutation algorithm and, if I'm correct, they should always yield the same results.

Hope it can help somebody trying so hard to find an actual running solution.

public class Solution { 

    public static void main(String[] args) {
        test(uniqueDigitsBruteForce(5324), uniqueDigits(5324));
        test(uniqueDigitsBruteForce(5222), uniqueDigits(5222));
        test(uniqueDigitsBruteForce(5565), uniqueDigits(5565));
    }

     /**
     * A math version method to count numbers with distinct digits.
     * @param n
     * @return
     */
    static int uniqueDigits(int n) {
        int[] used = new int[10];
        String seq = String.valueOf(n);
        char[] ca = seq.toCharArray();
        int uniq = 0;

        for (int i = 1; i <= ca.length - 1; i++) {
            uniq += uniqueDigitsOfLength(i);
        }

        uniq += (getInt(ca[0]) - 1) * factorial(9) / factorial(9 - ca.length + 1);
        used[getInt(ca[0])] = 1;
        for (int i = 1; i < ca.length; i++) {
            int count = 0;
            for (int j = 0; j < getInt(ca[i]); j++) {
                if (used[j] != 1) count++;
            }
            uniq += count * factorial(9 - i) / factorial(9 - ca.length + 1);
            if (used[getInt(ca[i])] == 1)
                break;
            used[getInt(ca[i])] = 1;
        }

        if (isUniqueDigits(n)) {
            uniq += 1;
        }
        return uniq;
    }


    /**
     * A brute force version method to count numbers with distinct digits.
     * @param n
     * @return
     */
    static int uniqueDigitsBruteForce(int n) {
        int count = 0;
        for (int i = 1; i <= n; i++) {
            if (isUniqueDigits(i)) {
                count++;
            }
        }
        return count;
    }



    /**
     * http://oeis.org/A073531
     * @param n
     * @return
     */
    static int uniqueDigitsOfLength(int n) {
        if (n < 1) return 0;
        int count = 9;
        int numOptions = 9;
        while(--n > 0) {
            if (numOptions == 0) {
                return 0;
            }
            count *= numOptions;
            numOptions--;
        }
        return count;
    }

    /**
     * Determine if given number consists of distinct digits
     * @param n
     * @return
     */
    static boolean isUniqueDigits(int n) {
        int[] used = new int[10];
        if (n < 10) return true;
        while (n > 0) {
            int digit = n % 10;
            if (used[digit] == 1)
                return false;
            used[digit] = 1;
            n = n / 10;
        }
        return true;
    }

    static int getInt(char c) {
        return c - '0';
    }

    /**
     * Calculate Factorial
     * @param n
     * @return
     */
    static int factorial(int n) {
        if (n > 9) return -1;
        if (n < 2) return 1;
        int res = 1;            
        for (int i = 2; i <= n; i++) {
            res *= i;
        }
        return res;
    }

    static void test(int expected, int actual) {
        System.out.println("Expected Result: " + expected.toString());
        System.out.println("Actual Result: " + actual.toString());
        System.out.println(expected.equals(actual) ? "Correct" : "Wrong Answer");
    }
}