Count Digits

Q: Độ phức tạp thời gian của việc đếm chữ số là bao nhiêu?

Một số n có floor(log10(n)) + 1 chữ số, và vòng lặp thực hiện một phép chia cho mỗi chữ số, nên chạy trong thời gian O(log n) và dùng O(1) bộ nhớ. Với số nguyên 32-bit, vòng lặp chạy nhiều nhất 10 bước.

Q: Bạn có thể dùng log10 để đếm số chữ số của một số không?

Với n dương, số lượng là floor(log10(n)) + 1 , nhưng phép tính logarit sử dụng số dấu phẩy động. Phép tính này không xác định với 0, và khi gần một lũy thừa của 10, kết quả có thể bị làm tròn sai: log10(10^15-1) cho ra đúng 15 ở độ chính xác kép. Phép chia số nguyên luôn chính xác.

Người mớiToán và mô phỏng

+10

Cho một số nguyên không âm n, hãy trả về số chữ số của nó khi viết ở hệ cơ số 10, không tính các số 0 ở đầu. Số 0 được viết bằng một chữ số 0, nên nó có một chữ số.

Hàm

countDigits(n: integer) → integer

ninteger: số nguyên không âm dùng để đo
Trả vềinteger: số chữ số thập phân trong n

Ràng buộc

0 ≤ n ≤ 2³¹-1

Ví dụ

Đầu vào: n = 4096
Đầu ra: 4
Giải thích: Phép chia lấy phần nguyên cho 10 biến 4096 thành 409, 40 rồi 4: xóa ba chữ số, còn lại một chữ số, nên đáp án là 4.

Đầu vào: n = 0
Đầu ra: 1
Giải thích: 0 được viết bằng một chữ số. Vòng lặp đếm khi số lớn hơn 0 không bao giờ chạy trong trường hợp này và trả về 0 thay vì 1.

Đầu vào: n = 100
Đầu ra: 3
Giải thích: Số 0 cũng là chữ số: 100 được viết bằng 1, 0, 0, nên đáp án là 3.

Câu hỏi mở rộng

Bạn có thể đếm các chữ số mà không cần dùng vòng lặp chạy một lần cho mỗi chữ số, chẳng hạn bằng cách tìm kiếm nhị phân trên các lũy thừa của 10 không?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Mỗi phép chia lấy phần nguyên cho 10 sẽ bỏ đi một chữ số. Hãy đếm số lần chia cho đến khi còn lại một chữ số, rồi cộng thêm một cho chữ số đó. Lỗi thường xuất hiện ở các trường hợp biên: 0 có một chữ số, còn công thức logarit không hoạt động với 0 và một số giá trị nhỏ hơn một chút so với các lũy thừa lớn của 10.

Viết số bằng chữ và đếm số ký tự

Ý tưởng

Ngôn ngữ của bạn đã biểu diễn n ở hệ thập phân. Hãy yêu cầu chuỗi đó rồi đếm số ký tự: 4096 trở thành "4096", gồm bốn ký tự, còn 0 trở thành "0", nên không cần xử lý riêng số 0.

Phép chuyển đổi thực hiện một phép chia cho mỗi chữ số, vì vậy thời gian và bộ nhớ bổ sung đều là O(log n), tối đa 10 ký tự ở đây.

Thuật toán

Chuyển n thành chuỗi thập phân bằng một hàm (function) không bao giờ chuyển sang ký pháp khoa học.
Đếm số ký tự trong chuỗi.
Trả về số lượng đó. Với 0, chuỗi là "0", nên kết quả là 1 mà không cần kiểm tra thêm.

def countDigits(n):
    return len(str(n))

Chia cho 10 cho đến khi chỉ còn một chữ số

Ý tưởng

Bắt đầu đếm từ 1 và chia cho 10 khi n ≥ 10, mỗi lần chia thì cộng thêm 1. Bắt đầu từ 1 có nghĩa là mọi số đều có ít nhất một chữ số, đúng với quy tắc áp dụng cho 0, nên không cần kiểm tra riêng.

Vòng lặp chạy tối đa 9 lần với 2147483647: thời gian O(log n). Vòng lặp giữ một biến đếm và thay đổi bản sao của chính n, nên bộ nhớ bổ sung là O(1).

Thuật toán

Đặt count = 1 cho chữ số luôn có mặt.
Khi n ≥ 10, chia n cho 10 bằng phép chia lấy phần nguyên rồi tăng count thêm 1.
Khi chỉ còn một chữ số, trả về count.

def countDigits(n):
    count = 1  # every number, 0 included, has at least one digit
    while n >= 10:
        n //= 10
        count += 1
    return count

Lỗi thường gặp và trường hợp biên

Đếm từ 0 trong khi n > 0. Cách này trả về 0 khi n = 0.
Dùng floor(log10(n)) + 1. Cách này không hoạt động với 0, vì logarit bằng âm vô cực, và với 10^15-1, vì độ chính xác kép làm tròn logarit thành đúng 15, khiến công thức cho kết quả là 16 chữ số.
Phép chia thực trong JavaScript, Lua, PHP hoặc R, trong đó / giữ lại phần thập phân. Khi đó, vòng lặp while n > 0 chạy 328 lần với 4096. Hãy dùng Math.floor, math.floor, intdiv hoặc %/%.
Ký hiệu khoa học trong phiên bản chuỗi. R ghi as.character(1e5) thành "1e+05"; hãy dùng sprintf("%.0f", n). Trong Lua 5.3 trở lên, tostring(4096.0) vẫn giữ .0; hãy dùng string.format("%d", n).

Câu hỏi thường gặp3

Độ phức tạp thời gian của việc đếm chữ số là bao nhiêu?

Một số n có floor(log10(n)) + 1 chữ số, và vòng lặp thực hiện một phép chia cho mỗi chữ số, nên chạy trong thời gian O(log n) và dùng O(1) bộ nhớ. Với số nguyên 32-bit, vòng lặp chạy nhiều nhất 10 bước.

Bạn có thể dùng log10 để đếm số chữ số của một số không?

Với n dương, số lượng là floor(log10(n)) + 1, nhưng phép tính logarit sử dụng số dấu phẩy động. Phép tính này không xác định với 0, và khi gần một lũy thừa của 10, kết quả có thể bị làm tròn sai: log10(10^15-1) cho ra đúng 15 ở độ chính xác kép. Phép chia số nguyên luôn chính xác.

Làm thế nào để đếm các chữ số của một số âm?

Trước tiên, lấy giá trị tuyệt đối, sau đó đếm như bình thường. String(-42) có ba ký tự vì dấu trừ không phải là chữ số. Với số nguyên 32 bit nhỏ nhất, hãy lấy giá trị tuyệt đối bằng kiểu 64 bit, vì số đó không vừa trong 32 bit.

def countDigits(n):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

n = 4096

Đầu ra mong đợi