To pytanie wywiad.Biorąc pod uwagę liczbę n, dowiedzieć się, ile liczb ma cyfrę 2 w zakresie 0 ... n
Biorąc pod uwagę liczbę n, dowiedzieć się, ile mają numery cyfra 2 w zakresie 0 ... n
Na przykład
wejście wyjście = 13 = 2 (2 i 12)
Dałem zwykłe rozwiązanie O (n^2), ale czy istnieje lepsze podejście.
jest jakaś „sztuczka” formuła, która pomoże mi uzyskać odpowiedź od zaraz
Policz numery, które wykonują nie mieć cyfrę 2. Wśród liczb mniej niż 10 k istnieją dokładnie 9 k z nich. Wtedy pozostaje w leczeniu numery od 10 k do n, gdzie
10^k <= n < 10^(k+1)
które można zrobić traktując pierwsze cyfry indywidualnie (przypadki 2 i inni muszą być zróżnicowane), a następnie pierwszy 2 cyfry itp
na przykład dla n = 2345 znajdujemy istnieją 9^3 = 729 numery bez cyfrą 2 poniżej 1000. są to znowu 729 takich liczb w zakresie od 1000 do 1999. Następnie w zakresie od 2000 do 2345, nie są nieobecne, w sumie 1458, stąd liczby zawierające cyfrę 2 to
2345 - 1458 = 887
mógłbyś wyjaśnić, jak masz 9 liczb^K, nie jestem bardzo dobry z kombinatoryki. – nikhil
Jeśli piszesz liczby z zerami wiodącymi, numery od 0 do "10^k - 1" są dokładnie tymi liczbami, które można wpisać dokładnie za pomocą cyfr "k". Dla każdej cyfry dostępnych jest 9 ('== 10 - 1') możliwych wyborów (' 0,1,3,4,5,6,7,8,9'). Wybory są niezależne, więc całkowita liczba wyborów jest iloczynem liczby opcji dla każdej cyfry, '9 * 9 * ... * 9 = 9^k'. Gdybyśmy byli po liczbach nie zawierających ani cyfry 2, ani cyfry 5, byłaby to "8^k" (8 = 10 - 2). Ta sama zasada obowiązuje dla reprezentacji liczb w innych podstawach. Ponieważ jednak liczby nie mają początkowych zer, cd ... –
..., zabronienie cyfry 0 jest nieco inne. Następnie nie możesz dodać zer wiodących, aby wszystkie liczby miały tę samą długość, a liczba cyfr poniżej "10^k", które nie mają cyfry 0, wynosi "9^1 + 9^2 + 9^3 + ... + 9^k = 9 * (9^k - 1)/8'. Jeśli zabronisz 0 i "d" innych cyfr, pozostawiając cyfry "e = 9-d", otrzymasz 'e^1 + e^2 + ... + e^k = e * (e^k - 1)/(e-1) '. (Zastąp 9 przez 'base-1' dla zasad innych niż 10.) –
Biorąc pod uwagę liczbę z cyframi ABCDEF można policzyć liczbę "2 w zakresach [0,F], [0,E9], [0,D99], [0,C999], [0,B9999] i [0,A99999] i dodać je.
W przypadku zakresu [0, X9999...999] najwyższy numer T = X9999...999 można zapisać jako (X+1) * 10<sup>nines</sup> -1.
liczba „2 jest w tym zakresie są:
((X >= 2 ? 1/(X + 1)) : 0) + nines/10) * (T + 1);
że: jeśli X >= 2 frakcję liczb, które mają«2»w dziewiątkami pozycji +1 jest 1/(X+1) w sumie istnieją (T+1)/(X+1) '2's na tej pozycji. Jeśli X < 2, wtedy żadna liczba na [0..T] nie ma "2" w tej pozycji.
Na pozostałych pozycjach cyfr, to łatwo zauważyć, że w każdej pozycji cyfr, 1/10 numerów mają „2”, więc istnieje (T+1)/10 „2 na pierwszej pozycji 0, (T+1)/10” 2'S w pozycji 1, itp ogółem, (T+1) * nines/10.
Złożoność tego rozwiązania to O (logN).
to jak pójdę temat kodowania mój pierwszy projekt (kod Pythona)
def count2(n) :
return [p for p in range(n+1) if '2' in str(p)]
i że zwróci Ci listę z numerem zawierającym.
Pod względem wydajności nie jest tak źle, dla n = 10000000 średnio iteracja trwa około 5,5 sekundy
argumentem „cyfra” jest ten, który chcemy policzyć i arg „liczba” jest aż gdzie chcesz policzyć. Dla np .: Jeśli chcemy policzyć wystąpienia "1", od 0 do 12, wywołaj funkcję z cyfrą = 1 i liczbą = 12, i zwróci liczbę wystąpień "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;
}
Wyjaśnij to z pewnym wyjaśnieniem. – Sankarann
countOccurrences (1,20) = 3; // źle – SMUsamaShah
Czy próbowałeś wykonać tę metodę? Zwraca 12, na countOccurrences (1,20), a nie 3. – undeadlock
O (n²)? Jeśli masz na myśli generowanie liczb i sprawdzanie cyfr, to jest to O (n lg n), ponieważ każda liczba n jest reprezentowana przez cyfry O (lg n). –
To kwestia permuttation .. –