Happy Number

Q: Độ phức tạp thời gian của số hạnh phúc là gì?

O(log n) . Bước đầu tiên đọc O(log n) chữ số của n ; mọi giá trị sau đó đều nhỏ hơn 1000, nên mỗi lần đi qua không quá 20 số trước khi đến 1 hoặc lặp lại. Tập hợp băm lưu các số đó, còn phiên bản Floyd dùng O(1) bộ nhớ.

DễCon trỏ nhanh và chậm Băm

+10

Bắt đầu với một số nguyên dương n rồi thay nó bằng tổng bình phương các chữ số của nó, lặp đi lặp lại. Ví dụ, 12 trở thành 1² + 2² = 5. Nếu quá trình này đạt đến 1, thì n là số hạnh phúc; nếu không, nó sẽ lặp mãi qua các số không bao giờ gồm 1. Trả về true nếu n là số hạnh phúc và false nếu không phải.

Hàm

isHappy(n: integer) → boolean

ninteger: số nguyên dương cần kiểm tra
Trả vềboolean: đúng nếu lặp lại phép tính tổng bình phương các chữ số cho đến khi được 1, sai nếu phép tính lặp vô hạn

Ràng buộc

1 ≤ n ≤ 2³¹-1

Ví dụ

Đầu vào: n = 7
Đầu ra: true
Giải thích: 7 trở thành 49, sau đó 4² + 9² = 97, rồi 130, rồi 10, rồi 1. Quá trình đạt đến 1, nên 7 là số hạnh phúc.

Đầu vào: n = 2
Đầu ra: false
Giải thích: 2 trở thành 4, 16, 37, 58, 89, 145, 42, 20 rồi lại thành 4. Từ đó, tám số tương tự lặp lại mãi và không bao giờ đạt đến 1.

Đầu vào: n = 100
Đầu ra: true
Giải thích: 1² + 0² + 0² = 1, vì vậy 100 đạt đến 1 sau một bước.

Câu hỏi mở rộng

Làm thế nào để đếm nhanh các số hạnh phúc từ 1 đến 10^6, tái sử dụng kết quả cho các số nhỏ hơn 1000 thay vì bắt đầu lại từ đầu với từng số?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Quá trình lặp không thể tăng vô hạn: một số có 10 chữ số ánh xạ thành giá trị nhiều nhất là 10 × 81 = 810, còn số nhỏ hơn 1000 ánh xạ thành giá trị nhiều nhất là 243. Vì vậy, nó luôn nằm trong nhóm có ít hơn 1000 giá trị và phải đạt đến 1 hoặc lặp lại. Đây là bài toán phát hiện chu trình: ghi nhớ những gì bạn đã thấy, hoặc cho một con trỏ chậm và một con trỏ nhanh cùng di chuyển.

Hãy nhớ mọi con số bạn đã thấy

Ý tưởng

Lưu mọi số bạn gặp vào một tập hợp băm và dừng khi gặp số 1 hoặc gặp lại một số đã có. Số tiếp theo chỉ phụ thuộc vào số hiện tại, vì vậy khi một số xuất hiện lại, mọi số sau đó cũng sẽ lặp lại và số 1 không thể xuất hiện. Với số 2, tập hợp sẽ chứa các số 2, 4, 16, 37, 58, 89, 145, 42 và 20, còn giá trị tiếp theo là 4 đã có trong tập hợp.

Sau bước đầu tiên, mọi giá trị đều nhỏ hơn 1000, vì vậy có thể dùng mảng cờ gồm 1000 phần tử thay cho tập hợp.

Thuật toán

Tạo một tập hợp băm rỗng seen.
Khi n khác 1, trả về false nếu n nằm trong seen.
Nếu không, thêm n vào seen và thay n bằng tổng bình phương các chữ số của nó.
Khi vòng lặp kết thúc, n bằng 1: trả về true.

def digitSquareSum(n):
    total = 0
    while n > 0:
        digit = n % 10
        total += digit * digit
        n //= 10
    return total


def isHappy(n):
    seen = set()
    while n != 1:
        if n in seen:
            return False  # back at an earlier number: a loop without 1
        seen.add(n)
        n = digitSquareSum(n)
    return True

Con trỏ nhanh và chậm (phát hiện chu trình Floyd)

Ý tưởng

Mỗi số có một mũi tên trỏ đến tổng bình phương các chữ số của nó, vì vậy đường đi bắt đầu từ n sẽ đến 1 hoặc đi vào một vòng lặp. Phương pháp Floyd tìm vòng lặp mà không cần lưu trữ: slow đi một bước mỗi lượt, còn fast đi hai bước.

Nếu vòng lặp không chứa 1, cả hai con trỏ đều đi vòng quanh nó, và mỗi lượt fast tiến thêm một bước, nên chúng gặp nhau tại cùng một số: với 2, chúng gặp nhau ở 42 sau bảy lượt. Nếu đường đi đến 1, fast đến đó trước và dừng lại, vì 1 ánh xạ thành 1. Với 7, fast đi qua 49, 130, 1 trong khi slow vẫn ở 97. Số lượt chỉ bằng một bội số nhỏ của độ dài đường đi, còn bộ nhớ cần dùng là hai số nguyên.

Thuật toán

Viết một hàm trợ giúp trả về tổng bình phương các chữ số của một số.
Đặt slow = n và đặt fast là số ở vị trí cách n một bước.
Trong khi fast không phải là 1 và slow khác fast, di chuyển slow một bước và fast hai bước.
Trả về kết quả cho biết fast có bằng 1 hay không.

def digitSquareSum(n):
    total = 0
    while n > 0:
        digit = n % 10
        total += digit * digit
        n //= 10
    return total


def isHappy(n):
    slow = n
    fast = digitSquareSum(n)
    # fast moves two steps for every step of slow; they meet only inside a loop.
    while fast != 1 and slow != fast:
        slow = digitSquareSum(slow)
        fast = digitSquareSum(digitSquareSum(fast))
    return fast == 1

Lỗi thường gặp và trường hợp biên

Lặp cho đến khi giá trị bằng 1 mà không có lối thoát nào khác. Với 2, vòng lặp đó không bao giờ kết thúc.
Bắt đầu cả hai con trỏ ở cùng một số và kiểm tra slow != fast trước bước di chuyển đầu tiên. Vòng lặp không chạy, và 7 bị kết luận là số không hạnh phúc.
Trả về slow == 1. Với 7, fast đạt đến 1 và vòng lặp dừng khi slow đang ở 97.
Kết luận n là số không hạnh phúc mỗi khi hai con trỏ gặp nhau. Chúng cũng gặp nhau ở 1, vì vậy hãy kiểm tra vị trí chúng gặp nhau.
Cộng các chữ số, hoặc bình phương cả số. Với 12, giá trị tiếp theo là 1² + 2² = 5, không phải 3 hay 144.

Câu hỏi thường gặp3

Độ phức tạp thời gian của số hạnh phúc là gì?

O(log n). Bước đầu tiên đọc O(log n) chữ số của n; mọi giá trị sau đó đều nhỏ hơn 1000, nên mỗi lần đi qua không quá 20 số trước khi đến 1 hoặc lặp lại. Tập hợp băm lưu các số đó, còn phiên bản Floyd dùng O(1) bộ nhớ.

Tại sao mọi số không hạnh phúc đều cuối cùng đi đến 4?

Kiểm tra mọi số dưới 1000 cho thấy có một vòng lặp không chứa 1: 4, 16, 37, 58, 89, 145, 42, 20 rồi quay lại 4. Mọi số bắt đầu đều giảm xuống dưới 1000 sau một bước, nên mọi số không hạnh phúc đều rơi vào vòng lặp này. Dừng ở 4 là được, nhưng khi phỏng vấn, bạn sẽ phải giải thích lý do.

Số hạnh phúc có liên quan gì đến chu trình danh sách liên kết?

Cả hai đều hỏi liệu đi theo một mũi tên từ mỗi phần tử có đưa ta quay lại một phần tử đã ghé qua hay không. Ở đây, mũi tên là tổng bình phương các chữ số; trong danh sách liên kết, đó là con trỏ đến phần tử tiếp theo. Vì vậy, hai con trỏ nhanh và chậm đều giải được cả hai bài toán chỉ với bộ nhớ hằng số.

def isHappy(n):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

n = 7

Đầu ra mong đợi

true