Số hạnh phúc trong Python

Số hạnh phúc: bắt đầu từ số dương, thay thế bằng tổng bình phương các chữ số, lặp lại cho đến khi được 1 (hạnh phúc) hoặc lặp vô tận (không hạnh phúc). Ví dụ: 19 → 1^2+9^2=82 → 8^2+2^2=68 → 6^2+8^2=100 → 1^2+0^2+0^2=1 → true.

Giải pháp

Sử dụng đệ quy với bộ nhớ (dynamic programming):

• Base case: n=1 → true.
• Nếu n đã thăm → false.
• Đánh dấu n đã thăm.
• Chuyển n thành chuỗi, tách chữ số, tính tổng bình phương → temp.
• Gọi đệ quy với temp.

Ví dụ

Triển khai Python:

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) 
ob1 = Solution() 
op = ob1.isHappy(19) 
print("Is Happy:",op)

Đầu vào

19

Đầu ra

Is Happy: True