È una domanda di intervista.Dato un numero n, scopri quanti numeri hanno la cifra 2 nell'intervallo 0 ... n
Dato un numero n, scoprire quanti numeri hanno cifre 2 nell'intervallo 0 ... n
Ad esempio,
input = 13 output = 2 (2 e 12)
Ho dato la solita soluzione O (n^2) ma c'è un approccio migliore.
v'è alcuna formula 'trucco' che mi aiuterà a ottenere la risposta giusta via
Contare i numeri che fare non hanno la cifra 2. Tra i numeri meno di 10 k, ci sono esattamente 9 k di loro. Poi rimane per trattare i numeri da 10 k a n, dove
10^k <= n < 10^(k+1)
che si può fare trattando la prima cifra singolarmente (casi 2 e altri devono essere differenziate), e quindi il primo 2 cifre ecc.
Ad esempio, per n = 2345, troviamo che ci sono numeri 9^3 = 729 senza la cifra 2 sotto 1000. Ci sono ancora 729 numeri nella gamma da 1000 a 1999. Quindi nella gamma da 2000 a 2345, lì sono nessuno, per un totale di 1458, quindi i numeri contenenti la cifra 2 sono
2345 - 1458 = 887
Puoi spiegare come hai ottenuto i numeri 9^k, non sono molto bravo con il combinatorio. – nikhil
Se si scrivono numeri con zeri iniziali, i numeri da 0 a '10^k - 1' sono precisamente i numeri che si possono scrivere con cifre esattamente' k'. Per ciascuna delle cifre, ci sono 9 ('== 10 - 1') scelte possibili (' 0,1,3,4,5,6,7,8,9'). Le scelte sono indipendenti, quindi il numero totale di scelte è il prodotto del numero di scelte per ogni cifra, '9 * 9 * ... * 9 = 9^k'. Se cercassi i numeri che non contengono né una cifra 2 né una cifra 5, sarebbe '8^k' (8 = 10 - 2). Lo stesso principio vale per le rappresentazioni di numeri in altre basi. Tuttavia, poiché i numeri non hanno realmente zero iniziali, cont ... –
..., vietare la cifra 0 è leggermente diverso. Quindi non puoi aggiungere zeri iniziali per ottenere tutti i numeri alla stessa lunghezza, e il conteggio dei numeri sotto "10^k" che non hanno una cifra 0 è '9^1 + 9^2 + 9^3 + ... + 9^k = 9 * (9^k - 1)/8'. Se si proibisce 0 e 'd' altre cifre, lasciando le cifre' e = 9-d' ammissibili, si ottiene 'e^1 + e^2 + ... + e^k = e * (e^k - 1)/(e-1) '. (Sostituisci 9 con 'base-1' per basi diverse da 10.) –
Dato il numero con le cifre ABCDEF è possibile contare il numero di "2" negli intervalli [0,F], [0,E9], [0,D99], [0,C999], [0,B9999] e [0,A99999] e aggiungerli.
Quindi per l'intervallo [0, X9999...999], il numero superiore T = X9999...999 può essere scritto come (X+1) * 10<sup>nines</sup> -1.
Il numero di '2 del in tale intervallo è:
((X >= 2 ? 1/(X + 1)) : 0) + nines/10) * (T + 1);
Cioè: se X >= 2, la frazione di numeri che hanno un '2' le nove posizioni + 1 è 1/(X+1), in totale ci sono (T+1)/(X+1) '2 in quella posizione. Se X < 2, quindi nessun numero su [0..T] ha un '2' in quella posizione.
Per le altre posizioni di cifra, è facile vedere che ad ogni posizione di cifra, 1/10 dei numeri hanno un '2', quindi ci sono (T+1)/10 '2 della struttura posizione 0, (T+1)/10' 2'S posizione 1, ecc totale, (T+1) * nines/10.
La complessità di questa soluzione è O (logN).
questo è come andrei di codifica il mio primo progetto (codice Python)
def count2(n) :
return [p for p in range(n+1) if '2' in str(p)]
e che restituirà un elenco con il numero che contiene.
In termini di prestazioni non è poi così male, per n = 10.000.000 un'iterazione media è di circa 5,5 secondi
argomento 'cifre' è quella che vogliamo contare e arg 'numero' è fino a dove siamo voglio contare. Ad esempio: se vogliamo contare le occorrenze di '1', da 0 a 12, chiama la funzione con digit = 1 e number = 12, e restituirà il numero di occorrenze di '1'.
int countOccurrences(int digit, int number)
{
int counter = 0;
for(int i=1; i<number; i++)
{
int j = i;
while(j > 0)
{
if(j%10 == digit)
counter++;
j /= 10;
}
}
return counter;
}
Spiegarlo con alcune spiegazioni .. – Sankarann
countOccurrences (1,20) = 3; // errato – SMUsamaShah
Hai provato a eseguire questo metodo? Restituisce 12, su countOccurrences (1,20), non su 3. – undeadlock
O (n²)? Se si intende, generare i numeri e controllare le cifre, ovvero O (n lg n), poiché ciascun numero n è rappresentato da cifre O (lg n). –
È una domanda di permutazione .. –