โจทย์
แฟกทอเรียลของ n เขียนว่า n! คือ 1 × 2 × … × n โดยนิยาม 0! = 1
ให้เขียนฟังก์ชัน factorial(n)
อินพุต
n: จำนวนเต็มที่ไม่เป็นลบ
เอาต์พุต
คืนค่า n!
เงื่อนไข
0 ≤ n ≤ 20 ดังนั้นผลลัพธ์จะอยู่ในช่วงของ signed 64-bit integer
ตัวอย่าง
ตัวอย่างที่ 1
อินพุต:
n = 5
ผลลัพธ์ที่คาดหวัง:
expected = 120
อินพุต:
long long n = 5;
ผลลัพธ์ที่คาดหวัง:
long long expected = 120;
อินพุต:
long n = 5;
ผลลัพธ์ที่คาดหวัง:
long expected = 120;
คำอธิบาย
1 × 2 × 3 × 4 × 5 = 120
ตัวอย่างที่ 2
อินพุต:
n = 0
ผลลัพธ์ที่คาดหวัง:
expected = 1
อินพุต:
long long n = 0;
ผลลัพธ์ที่คาดหวัง:
long long expected = 1;
อินพุต:
long n = 0;
ผลลัพธ์ที่คาดหวัง:
long expected = 1;
คำอธิบาย
0! ถูกนิยามให้เท่ากับ 1
แนวทางการแก้
ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ
คำใบ้ 1
factorial คือการคูณทุกจำนวนตั้งแต่ 1 ถึงเลขที่ให้มา
คำใบ้ 2
ใช้ตัวคูณสะสมแบบวนลูปก็พอ และ 0 มีค่าพิเศษที่กำหนดไว้
คำใบ้ 3
เพราะ input ไม่ใหญ่ ปัญหาหลักคือ overflow ในภาษาอื่น
ความซับซ้อนที่คาดหวัง
เวลา O(n), หน่วยความจำเพิ่ม O(1)