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

#include<bits/stdc++.h>
 using namespace std;
 #define int long long
 int dp[19][2048][2];
 
 int func(int pos, string &num,int mask, int tight){
    if(pos == -1)
        return 1;
    if(dp[pos][mask][tight] != -1)
        return dp[pos][mask][tight];
    int ans=0;
    int d = num[num.length()-pos-1]-'0';
    if((1LL<<d)& mask)
        dp[pos][mask][tight]=0;
    int x = (tight ? d : 9);
    
    for(int i=0;i<=x;i++)
    {
        ans += func(pos-1, num, mask+(1LL<<d), (i==x));
    }
    return dp[pos][mask][tight] = ans;
 }
 
 signed main()
 {
    // for(int i=0;i<19;i++)
    // {
        // for(int j=0;j<2048;j++)
        // {
            // dp[i][j][0]=dp[i][j][1]=-1;
        // }
    // }
    memset(dp,-1,sizeof(dp));
    int l,r;
    cin>>l>>r;
    string num = to_string(r);
    int val1  = func(num.length()-1, num, 0, 1);
    memset(dp,-1,sizeof(dp));
    // l=l-1;
    string temp = to_string(l);
    cout<<temp<<endl;
    int val2 = func(num.length()-1,temp,0,1);
    int res= val1-val2;
    cout<<res<<endl;
 }
 

Answer 2

Here is what you want, implemented by Python

def numDistinctDigitsAtMostN(n):
    nums = [int(i) for i in str(n+1)]
    k = len(str(n+1))
    res = 0
    # Here is a paper about Number of n-digit positive integers with all digits distinct
    # http://oeis.org/A073531
    # a(n) = 9*9!/(10-n)!

    # calculate the number of n-digit positive integers with all digits distinct
    for i in range(1, k):
        res += 9 * math.perm(9,i-1)

    # count no duplicates for numbers with k digits and smaller than n
    for i, x in enumerate(nums):
        if i == 0:
            digit_range = range(1,x) # first digit can not be 0
        else:
            digit_range = range(x)

        for y in digit_range:
            if y not in nums[:i]:
                res += math.perm(9-i,k-1-i)
        if x in nums[:i]:
            break
    return res

And here are some good test cases. They are big enough to test my code.

numDistinctDigitsAtMostN(100) = 90 #(9+81)
numDistinctDigitsAtMostN(5853) = 3181
numDistinctDigitsAtMostN(5853623) = 461730
numDistinctDigitsAtMostN(585362326) = 4104810

Answer 3

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 4

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 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");
    }
}

Answer 6

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution { 
 public static void main(String[] args) {

         int rem;
        Scanner in=new Scanner(System.in);
         int num=in.nextInt();
    int length = (int)(Math.log10(num)+1);//This one is to find the length of the number i.e number of digits of a number


    int arr[]=new int[length]; //Array to store the individual numbers of a digit for example 123 then we will store 1,2,3 in the array

    int count=0;
     int i=0;

     while(num>0)           //Logic to store the digits in array
    { rem=num%10;   
        arr[i++]=rem;
        num=num/10; 
    }     
    for( i=0;i<length;i++)          //Logic to find the duplicate numbers
    {
        for(int j=i+1;j<length;j++)
        {
            if(arr[i]==arr[j])
            {
                count++;
                 break;
            }
        }
    }
     //Finally total number of digits minus duplicates gives the output
     System.out.println(length-count);
   }
}

Answer 7

Lazy man's DP:

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

Answer 8

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