โจทย์
n! = 1 × 2 × ... × n โตเร็วกว่าการยกกำลังใด ๆ แค่ 25! ก็มี 26 หลักแล้ว ให้คำนวณ n! อย่างแม่นยำแล้วหาผลรวมของเลขโดด ถ้าภาษาที่ใช้ไม่มีจำนวนเต็มขนาดใหญ่ ก็เก็บจำนวนเป็นอาร์เรย์ของเลขโดด แล้วคูณด้วย 2, 3, ..., n ไปตามลำดับ
จงเขียนฟังก์ชัน factorial_digit_sum(n)
อินพุต
n: จำนวนที่ต้องการหาแฟกทอเรียล
เอาต์พุต
คืนค่าผลรวมของเลขโดดฐานสิบของ n! โดยจำไว้ว่า 0! = 1
เงื่อนไข
0 ≤ n ≤ 1000
ตัวอย่าง
อินพุต:
n = 5
ผลลัพธ์ที่คาดหวัง:
expected = 3
อินพุต:
long long n = 5;
ผลลัพธ์ที่คาดหวัง:
long long expected = 3;
อินพุต:
long n = 5;
ผลลัพธ์ที่คาดหวัง:
long expected = 3;
คำอธิบาย
5! = 120 และ 1 + 2 + 0 = 3
อินพุต:
n = 0
ผลลัพธ์ที่คาดหวัง:
expected = 1
อินพุต:
long long n = 0;
ผลลัพธ์ที่คาดหวัง:
long long expected = 1;
อินพุต:
long n = 0;
ผลลัพธ์ที่คาดหวัง:
long expected = 1;
คำอธิบาย
ตามนิยาม 0! เท่ากับ 1 คำตอบจึงเป็น 1
แนวทางการแก้
ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ
คำใบ้ 1
เริ่มจาก 1 แล้วคูณด้วย 2, 3, ..., n
คำใบ้ 2
คูณเลขโดดแต่ละตัว บวกตัวทด เก็บหลักสุดท้ายไว้ แล้วทดส่วนที่เหลือไป
คำใบ้ 3
ถ้ายังมีตัวทดเหลืออยู่ตอนท้าย ตัวทดนั้นจะกลายเป็นเลขโดดตัวใหม่
ความซับซ้อนที่คาดหวัง
เวลา O(n × D) โดย D คือจำนวนหลักของ n!, หน่วยความจำเพิ่ม O(D)
แหล่งอ้างอิง
โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน