โจทย์
ช่างทำป้ายคนหนึ่งรับทำป้ายบ้านเลขที่ที่สะกดตัวเลขออกมาเป็นคำ และคิดเงินตามจำนวนตัวอักษร ให้เขียนทุกจำนวนตั้งแต่ 1 ถึง n เป็นภาษาอังกฤษแบบอเมริกันโดยไม่มีคำว่า "and" เช่น 342 คือ "three hundred forty-two" และ 2005 คือ "two thousand five" ช่องว่างและยัติภังค์ไม่คิดเงิน นับเฉพาะตัวอักษรเท่านั้น
จงเขียนฟังก์ชัน number_letter_counts(n)
การสะกดที่ใช้ ได้แก่ one ถึง nineteen, twenty, thirty, forty, fifty, sixty, seventy, eighty, ninety, hundred, thousand จำนวนตั้งแต่ 1,000 ขึ้นไปเขียนเป็นส่วนหลักพัน (สะกดเป็นคำเช่นกัน สูงสุดถึง ninety-nine) ตามด้วย "thousand" แล้วจึงตามด้วยส่วนที่เหลือ (ถ้ามี)
อินพุต
n: จำนวนสุดท้ายที่ต้องเขียน
เอาต์พุต
คืนค่าจำนวนตัวอักษรทั้งหมดที่ใช้เขียน 1, 2, ..., n ถ้า n = 0 จะไม่มีการเขียนอะไรเลยและคำตอบคือ 0
เงื่อนไข
0 ≤ n ≤ 99,999
ตัวอย่าง
อินพุต:
n = 3
ผลลัพธ์ที่คาดหวัง:
expected = 11
อินพุต:
long long n = 3;
ผลลัพธ์ที่คาดหวัง:
long long expected = 11;
อินพุต:
long n = 3;
ผลลัพธ์ที่คาดหวัง:
long expected = 11;
คำอธิบาย
"one", "two" และ "three" มีตัวอักษร 3 + 3 + 5 = 11 ตัว
อินพุต:
n = 21
ผลลัพธ์ที่คาดหวัง:
expected = 121
อินพุต:
long long n = 21;
ผลลัพธ์ที่คาดหวัง:
long long expected = 121;
อินพุต:
long n = 21;
ผลลัพธ์ที่คาดหวัง:
long expected = 121;
คำอธิบาย
1 ถึง 19 ใช้ตัวอักษร 106 ตัว twenty เพิ่มอีก 6 และ twenty-one เพิ่มอีก 9 รวมเป็น 121
แนวทางการแก้
ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ
คำใบ้ 1
ใช้ตารางสำหรับ 1 ถึง 19 แล้วใช้คำหลักสิบสำหรับ 20 ถึง 90
คำใบ้ 2
กลุ่มสามหลักคือคำของหลักร้อย ตามด้วย "hundred" แล้วตามด้วยสองหลักสุดท้าย
คำใบ้ 3
สำหรับจำนวนตั้งแต่ 1,000 ขึ้นไป ให้สะกดกลุ่มหลักพัน เติม "thousand" แล้วสะกดส่วนที่เหลือ
ความซับซ้อนที่คาดหวัง
เวลา O(n), หน่วยความจำเพิ่ม O(1)
แหล่งอ้างอิง
โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน