โจทย์ทั้งหมด
ง่าย 0 ข้อที่แก้แล้ว อัตราผ่าน 0%

จำนวนแฮปปี้ (Happy Number)

ตัดสินว่าการนำกำลังสองของเลขโดดแต่ละหลักมารวมกันซ้ำไปเรื่อย ๆ จะไปถึง 1 หรือไม่

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

  • คำนวณผลรวมกำลังสองของเลขโดด
  • ตรวจจับลำดับที่วนซ้ำด้วยเซตหรือสองพอยน์เตอร์
  • หยุดลูปเมื่อเงื่อนไขใดเงื่อนไขหนึ่งในสองข้อเป็นจริง

โจทย์

เริ่มจากจำนวนเต็มบวกจำนวนหนึ่ง แล้วแทนที่ด้วยผลรวมกำลังสองของเลขโดดแต่ละหลัก ทำแบบนี้ซ้ำไปเรื่อย ๆ ถ้าในที่สุดได้ 1 จำนวนเริ่มต้นนั้นเป็น จำนวนแฮปปี้ (happy number) มิฉะนั้นกระบวนการจะวนลูปไปตลอดโดยไม่มี 1 อยู่ในวงเลย และจำนวนนั้นไม่ใช่จำนวนแฮปปี้ เช่น 7 → 49 → 97 → 130 → 10 → 1 ดังนั้น 7 เป็นจำนวนแฮปปี้

จงเขียน happy_number(n)

คุณต้องมีวิธีสังเกตว่าลำดับเริ่มวนซ้ำแล้ว เพื่อให้ลูปหยุดได้แม้กับจำนวนที่ไม่ใช่จำนวนแฮปปี้

อินพุต

n: จำนวนเริ่มต้น

เอาต์พุต

คืนค่า true ถ้ากระบวนการไปถึง 1 มิฉะนั้นคืนค่า false ตัวเลข 1 เองก็นับเป็นจำนวนแฮปปี้

เงื่อนไข

1 ≤ n ≤ 10^9

ตัวอย่าง

ตัวอย่างที่ 1
อินพุต:
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

ตัวอย่างที่ 2
อินพุต:
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 กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน

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

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

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

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

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