Cho số n, tìm hiểu xem có bao nhiêu số có chữ số 2 trong khoảng 0 ... n

Question

Đó là một câu hỏi phỏng vấn.

Cho một số n, tìm hiểu có bao nhiêu số có chữ số 2 trong khoảng 0 ... n

Ví dụ,

input = 13 output = 2 (2 và 12)

Tôi đã đưa ra giải pháp O (n^2) thông thường nhưng có cách tiếp cận tốt hơn.

là có bất kỳ công thức 'lừa' rằng sẽ giúp tôi để có được câu trả lời ngay lập tức

Answer 1

Đếm những con số mà làm không có chữ số 2. Trong số những con số ít hơn 10 ^k, có chính xác 9 ^k trong số đó. Sau đó, nó vẫn đối xử với những con số từ 10 ^k-n, nơi

10^k <= n < 10^(k+1) 

mà bạn có thể làm bằng cách xử lý các chữ số đầu tiên cá nhân (trường hợp 2 và những người khác phải được phân biệt), và sau đó là 2 đầu tiên các chữ số vv

Ví dụ: đối với n = 2345, chúng tôi thấy có 9^3 = 729 số không có chữ số 2 dưới 1000. Có 729 số đó trong khoảng từ 1000 đến 1999. Sau đó trong phạm vi từ 2000 đến 2345, ở đó là không, với tổng số 1458, do đó các số có chứa chữ số 2 là

2345 - 1458 = 887 

Answer 2

Cho số có chữ số ABCDEF bạn có thể đếm số '2 trong phạm vi [0,F], [0,E9], [0,D99], [0,C999], [0,B9999] và [0,A99999] và thêm chúng.

Sau đó, trong phạm vi [0, X9999...999], số đầu T = X9999...999 có thể được viết là (X+1) * 10<sup>nines</sup> -1.

Số 'của 2 trong phạm vi đó là:

((X >= 2 ? 1/(X + 1)) : 0) + nines/10) * (T + 1); 

Đó là: nếu X >= 2, phần của số đó có một '2' tại nines vị trí + 1 là 1/(X+1), Hiện có (T+1)/(X+1) '2 tại vị trí đó. Nếu X < 2, thì không có số nào trên [0..T] có dấu '2' ở vị trí đó.

Đối với các vị trí chữ số khác, rất dễ dàng để thấy rằng tại mỗi vị trí chữ số, 1/10 của những con số có một '2', vì vậy có (T+1)/10 '2 tại vị trí 0, (T+1)/10' 2 tại vị trí 1, vv Trong tổng số, (T+1) * nines/10.

Độ phức tạp của giải pháp này là O (logN).

Answer 3

này là thế nào tôi sẽ đi về mã hóa dự thảo (mã Python) đầu tiên của tôi

def count2(n) : 
    return [p for p in range(n+1) if '2' in str(p)] 

và điều đó sẽ trả lại cho bạn một danh sách với số lượng chứa.

Xét về hiệu suất nó không phải là xấu, cho n = 10.000.000 một lần lặp trung bình mất khoảng 5,5 giây

Answer 4

luận 'chữ số' là một mà chúng tôi muốn đếm và arg 'số' là đến nơi chúng tôi muốn đếm. Ví dụ: Nếu chúng ta muốn đếm số lần xuất hiện của '1', từ 0 đến 12, hãy gọi hàm có chữ số = 1 và số = 12, và nó sẽ trả về số lần xuất hiện của '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; 
}