Đề bài
Một thợ làm biển viết số nhà bằng chữ và tính tiền theo từng chữ cái. Hãy viết mọi số từ 1 đến n bằng tiếng Anh kiểu Mỹ, không dùng từ "and": 342 là "three hundred forty-two" và 2005 là "two thousand five". Dấu cách và dấu gạch nối không tính tiền; chỉ đếm chữ cái.
Hãy viết number_letter_counts(n).
Cách viết: one đến nineteen, twenty, thirty, forty, fifty, sixty, seventy, eighty, ninety, hundred, thousand. Các số từ 1,000 trở lên được viết thành phần nghìn (cũng viết bằng chữ, tối đa ninety-nine), tiếp theo là "thousand" rồi đến phần còn lại, nếu có.
Đầu vào
n: Số cuối cùng cần viết.
Đầu ra
Trả về tổng số chữ cái dùng cho 1, 2, ..., n. Với n = 0 thì không viết gì và đáp án là 0.
Ràng buộc
0 ≤ n ≤ 99,999
Ví dụ
Đầu vào:
n = 3
Kết quả mong đợi:
expected = 11
Đầu vào:
long long n = 3;
Kết quả mong đợi:
long long expected = 11;
Đầu vào:
long n = 3;
Kết quả mong đợi:
long expected = 11;
Giải thích
"one", "two" và "three" có 3 + 3 + 5 = 11 chữ cái.
Đầu vào:
n = 21
Kết quả mong đợi:
expected = 121
Đầu vào:
long long n = 21;
Kết quả mong đợi:
long long expected = 121;
Đầu vào:
long n = 21;
Kết quả mong đợi:
long expected = 121;
Giải thích
Từ 1 đến 19 dùng 106 chữ cái, twenty thêm 6 và twenty-one thêm 9, tổng cộng 121.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Xử lý 1 đến 19 bằng một bảng, rồi đến các từ hàng chục cho 20 đến 90.
Gợi ý 2
Một khối ba chữ số gồm từ hàng trăm, thêm "hundred", rồi đến hai chữ số cuối.
Gợi ý 3
Với các số từ 1,000 trở lên, đọc khối hàng nghìn, thêm "thousand", rồi đọc phần còn lại.
Độ phức tạp mong đợi
thời gian O(n), bộ nhớ phụ O(1)
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.