โจทย์
ทุกคนจะจับมือกับทุกคนอื่นเพียงครั้งเดียว การจับมือระหว่าง A กับ B ถือเป็นเหตุการณ์เดียวกับ B กับ A และไม่มีใครจับมือกับตัวเอง
ให้เขียนฟังก์ชัน handshake_count(people)
อินพุต
people: จำนวนคนทั้งหมด
เอาต์พุต
คืนค่าจำนวนการจับมือที่แตกต่างกันทั้งหมด
เงื่อนไข
0 ≤ people ≤ 1,000,000,000 คำตอบอยู่ในช่วงของจำนวนเต็ม signed 64-bit
ตัวอย่าง
ตัวอย่างที่ 1
อินพุต:
people = 4
ผลลัพธ์ที่คาดหวัง:
expected = 6อินพุต:
long long people = 4;
ผลลัพธ์ที่คาดหวัง:
long long expected = 6;อินพุต:
long people = 4;
ผลลัพธ์ที่คาดหวัง:
long expected = 6;คำอธิบาย
คู่ที่จับมือกันคือ AB, AC, AD, BC, BD และ CD รวมเป็นหกครั้ง
ตัวอย่างที่ 2
อินพุต:
people = 1
ผลลัพธ์ที่คาดหวัง:
expected = 0อินพุต:
long long people = 1;
ผลลัพธ์ที่คาดหวัง:
long long expected = 0;อินพุต:
long people = 1;
ผลลัพธ์ที่คาดหวัง:
long expected = 0;คำอธิบาย
มีคนเพียงคนเดียวจึงไม่มีใครให้จับมือด้วย
แนวทางการแก้
ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ
คำใบ้ 1
การจับมือหนึ่งครั้งคือคู่ของคน 2 คนที่ไม่เรียงลำดับ
คำใบ้ 2
นับจำนวนคู่ที่สร้างได้จากทุกคน โดยไม่ให้นับซ้ำ
คำใบ้ 3
ระวังว่า ถ้ามี 0 หรือ 1 คน จะไม่มีการจับมือเลย
ความซับซ้อนที่คาดหวัง
เวลา O(1), หน่วยความจำเพิ่ม O(1)
แหล่งอ้างอิง
โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน