Contare tutti i numeri con cifre univoche in un determinato intervallo

Question

Questa è una domanda di intervista. Contare tutti i numeri con cifre univoche (in decimale) nell'intervallo [1, N].

La soluzione ovvia è testare ciascun numero nell'intervallo se le sue cifre sono univoche. Possiamo anche generare tutti i numeri con cifre univoche (come permutazioni) e testare se sono nell'intervallo.

Ora mi chiedo se esiste una soluzione DP (programmazione dinamica) per questo problema.

Answer 1

sto pensando:

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 

Quindi:

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 

Aggiungere tutto quanto sopra fino ad arrivare al numero di cifre che N ha meno 1.

Poi si solo fare Number of unique digits numbers 1000-5324

E:

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 

Quindi:

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) 

Quanto sopra è qualcosa di simile:

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 

non si ha realmente bisogno DP come sopra dovrebbe essere abbastanza veloce.

EDIT:

Quanto sopra effettivamente deve essere un po 'più complicato (N [2] = 2 e N [3] = 2 non è valido). Ha bisogno di essere più simile a:

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

DP dell'uomo pigro:

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

Answer 3

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 4

Anche se questa questione era stata pubblicata nel 2013, mi sento come sia ancora degno di fornire un'implementazione di riferimento in quanto diverso dall'algoritmo fornito da Dukeling, non sono riuscito a trovare alcuna implementazione su Internet.

Ho scritto il codice in Java sia per la forza bruta che per l'algoritmo di permutazione di Dukeling e, se sono corretto, dovrebbero sempre produrre gli stessi risultati.

Spero che possa aiutare qualcuno a provare così tanto a trovare una soluzione funzionante.

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 5

Per un'interrogazione come questa, un algoritmo a forza bruta è probabilmente destinato a dimostrare la logica e la competenza di programmazione. Ma anche importante è dimostrare la conoscenza di un buon strumento per il lavoro.

Certo, dopo un sacco di tempo trascorso sul calcolo, è possibile trovare una formula matematica contorta per abbreviare un algoritmo di loop.Ma questa domanda è un semplice esempio di abbinamento di pattern, quindi perché non utilizzare lo strumento di abbinamento di pattern integrato in qualsiasi lingua che utilizzerai: espressioni regolari?

Ecco una soluzione estremamente semplice in C# come un esempio:

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

Linea 1 sarà diverso a seconda della lingua da utilizzare, ma è solo la creazione di un file CSV di tutti i numeri interi da 1 a N.

Ma la linea 2 sarebbe molto simile indipendentemente dalla lingua: contare quante volte il modello corrisponde al csv.

Il modello regex una cifra seguita eventualmente da alcune altre cifre, seguito da un duplicato del primo cifre.