Happy Numbers ใน Python

สมมติว่าเรามีตัวเลข n เราจะตรวจสอบว่ามันเป็น Happy Number หรือไม่ ตามที่รู้ Happy Number คือตัวเลขที่เริ่มจากจำนวนเต็มบวกใดๆ แทนที่ตัวเลขด้วยผลรวมของกำลังสองของหลักต่างๆ กระบวนการนี้จะทำซ้ำจนกลายเป็น 1 มิฉะนั้นจะวนรอบไม่สิ้นสุดในวงจร ตัวเลขเหล่านั้นเมื่อเจอ 1 จะเป็น Happy Number

ตัวอย่าง

อินพุตคือ 19 ผลลัพธ์จะเป็น true เนื่องจากเป็น Happy Number เราสามารถเห็นได้จาก 19 ว่า:

1² + 9² = 82

8² + 2² = 68

6² + 8² = 100

1² + 0² + 0² = 1

ขั้นตอนการแก้ปัญหา

ใช้แนวทาง Dynamic Programming และแก้ปัญหาแบบเรียกซ้ำ (recursion)
Base case: เมื่อ n = 1 ให้คืนค่า true
เมื่อ n ถูกเยี่ยมชมแล้ว ให้คืนค่า false
ทำเครื่องหมาย n ว่าเยี่ยมชมแล้ว
n := n เป็นสตริง, l := รายการของทุกหลักใน n
temp := ผลรวมกำลังสองของทุกหลัก
คืนค่าฟังก์ชันแบบเรียกซ้ำด้วยพารามิเตอร์ temp และรายการ visited

การใช้งาน

class Solution(object):
    def isHappy(self, n):
        return self.solve(n, {})
    def solve(self, n, visited):
        if n == 1:
            return True
        if n in visited:
            return False
        visited[n] = 1
        n = str(n)
        l = list(n)
        l = list(map(int, l))
        temp = 0
        for i in l:
            temp += (i**2)
        return self.solve(temp, visited)

ob = Solution()
print(ob.isHappy(19))

อินพุต

เอาต์พุต

True