โจทย์
เริ่มจากจำนวนเต็มบวกจำนวนหนึ่ง แล้วแทนที่ด้วยผลรวมกำลังสองของเลขโดดแต่ละหลัก ทำแบบนี้ซ้ำไปเรื่อย ๆ ถ้าในที่สุดได้ 1 จำนวนเริ่มต้นนั้นเป็น จำนวนแฮปปี้ (happy number) มิฉะนั้นกระบวนการจะวนลูปไปตลอดโดยไม่มี 1 อยู่ในวงเลย และจำนวนนั้นไม่ใช่จำนวนแฮปปี้ เช่น 7 → 49 → 97 → 130 → 10 → 1 ดังนั้น 7 เป็นจำนวนแฮปปี้
จงเขียน happy_number(n)
คุณต้องมีวิธีสังเกตว่าลำดับเริ่มวนซ้ำแล้ว เพื่อให้ลูปหยุดได้แม้กับจำนวนที่ไม่ใช่จำนวนแฮปปี้
อินพุต
n: จำนวนเริ่มต้น
เอาต์พุต
คืนค่า true ถ้ากระบวนการไปถึง 1 มิฉะนั้นคืนค่า false ตัวเลข 1 เองก็นับเป็นจำนวนแฮปปี้
เงื่อนไข
1 ≤ n ≤ 10^9
ตัวอย่าง
อินพุต:
n = 19
ผลลัพธ์ที่คาดหวัง:
expected = True
อินพุต:
long long n = 19;
ผลลัพธ์ที่คาดหวัง:
bool expected = true;
อินพุต:
long n = 19;
ผลลัพธ์ที่คาดหวัง:
bool expected = true;
คำอธิบาย
1² + 9² = 82 ต่อด้วย 8² + 2² = 68 ต่อด้วย 6² + 8² = 100 แล้ว 1² + 0² + 0² = 1 ดังนั้น 19 เป็นจำนวนแฮปปี้: true
อินพุต:
n = 4
ผลลัพธ์ที่คาดหวัง:
expected = False
อินพุต:
long long n = 4;
ผลลัพธ์ที่คาดหวัง:
bool expected = false;
อินพุต:
long n = 4;
ผลลัพธ์ที่คาดหวัง:
bool expected = false;
คำอธิบาย
4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 วนซ้ำโดยไม่เคยถึง 1 คำตอบจึงเป็น false
แนวทางการแก้
ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ
คำใบ้ 1
เขียนฟังก์ชันช่วยที่แปลงจำนวนหนึ่งเป็นผลรวมกำลังสองของเลขโดด
คำใบ้ 2
จำนวนที่ไม่ใช่จำนวนแฮปปี้จะวนกลับมาที่ค่าที่เคยได้แล้ว ให้จดค่าที่เคยเห็นไว้
คำใบ้ 3
ลำดับจะลดลงต่ำกว่าไม่กี่ร้อยอย่างรวดเร็ว เซตจึงมีขนาดเล็ก
ความซับซ้อนที่คาดหวัง
O(log n) ขั้นต่อหนึ่งจำนวน, หน่วยความจำเพิ่ม O(1) เมื่อใช้สองพอยน์เตอร์
แหล่งอ้างอิง
โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน