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