ง่าย 0 ข้อที่แก้แล้ว อัตราผ่าน 0%

Factorial Digit Sum

Add up the decimal digits of n factorial.

สิ่งที่คุณจะได้เรียนรู้

  • Multiply a digit array by a small number
  • Sum the digits of a large number
  • Remember that 0! = 1

โจทย์

ดูฉบับแปล

n! = 1 × 2 × ... × n grows faster than any power: 25! already has 26 digits. Compute n! exactly and add up its digits. Without big integers, store the number as an array of digits and multiply it by 2, 3, ..., n in turn.

Implement factorial_digit_sum(n).

Input

n: The number whose factorial is taken.

Output

Return the sum of the decimal digits of n!. Note that 0! = 1.

เงื่อนไข

0 ≤ n ≤ 1000

ตัวอย่าง

ตัวอย่างที่ 1
อินพุต:
n = 5

ผลลัพธ์ที่คาดหวัง:
expected = 3
อินพุต:
long long n = 5;

ผลลัพธ์ที่คาดหวัง:
long long expected = 3;
อินพุต:
long n = 5;

ผลลัพธ์ที่คาดหวัง:
long expected = 3;

คำอธิบาย

5! = 120 and 1 + 2 + 0 = 3.

ตัวอย่างที่ 2
อินพุต:
n = 0

ผลลัพธ์ที่คาดหวัง:
expected = 1
อินพุต:
long long n = 0;

ผลลัพธ์ที่คาดหวัง:
long long expected = 1;
อินพุต:
long n = 0;

ผลลัพธ์ที่คาดหวัง:
long expected = 1;

คำอธิบาย

0! is 1 by definition, so the answer is 1.

แนวทางการแก้

ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ

คำใบ้ 1

Start from 1 and multiply by 2, 3, ..., n.

คำใบ้ 2

Multiply each digit, add the carry, keep the last digit and carry the rest.

คำใบ้ 3

When the carry is still left over at the end, it becomes new digits.

ความซับซ้อนที่คาดหวัง

O(n × D) time where D is the digit count of n!, O(D) extra space

แหล่งอ้างอิง

โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน

คำตอบที่ผ่านดีที่สุดของแต่ละคน คำตอบที่เร็วกว่า ใช้หน่วยความจำน้อยกว่า และได้คะแนนดีกว่าจะอยู่ด้านบน

ยังไม่มีคำตอบที่ผ่าน แก้โจทย์นี้แล้วคว้าอันดับหนึ่งไปเลย

เรียนรู้จากคนอื่น

แนวทางจากชุมชน

ยังไม่มีวิธีทำที่เผยแพร่ ลองแก้โจทย์นี้เพื่อแชร์วิธีแรก