Đề bài
Bắt đầu từ một số nguyên dương, ta thay nó bằng tổng bình phương các chữ số của nó, và cứ tiếp tục làm như vậy. Nếu cuối cùng số đó trở thành 1 thì số ban đầu là số hạnh phúc. Nếu không, quá trình sẽ rơi vào một vòng lặp không bao giờ chứa 1, và số đó là số không hạnh phúc. Ví dụ, 7 → 49 → 97 → 130 → 10 → 1, nên 7 là số hạnh phúc.
Hãy viết happy_number(n).
Bạn cần một cách để nhận ra dãy số đã bắt đầu lặp lại, để vòng lặp cũng dừng được với những số không hạnh phúc.
Đầu vào
n: Số bắt đầu.
Đầu ra
Trả về true nếu quá trình đi đến 1, ngược lại trả về false. Bản thân số 1 là số hạnh phúc.
Ràng buộc
1 ≤ n ≤ 10^9
Ví dụ
Đầu vào:
n = 19
Kết quả mong đợi:
expected = True
Đầu vào:
long long n = 19;
Kết quả mong đợi:
bool expected = true;
Đầu vào:
long n = 19;
Kết quả mong đợi:
bool expected = true;
Giải thích
1² + 9² = 82, rồi 8² + 2² = 68, rồi 6² + 8² = 100, rồi 1² + 0² + 0² = 1, nên 19 là số hạnh phúc: true.
Đầu vào:
n = 4
Kết quả mong đợi:
expected = False
Đầu vào:
long long n = 4;
Kết quả mong đợi:
bool expected = false;
Đầu vào:
long n = 4;
Kết quả mong đợi:
bool expected = false;
Giải thích
4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 lặp lại mà không bao giờ đến được 1, nên kết quả là false.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Viết một hàm phụ biến một số thành tổng bình phương các chữ số của nó.
Gợi ý 2
Số không hạnh phúc sẽ lặp lại một giá trị đã xuất hiện trước đó; hãy ghi nhớ các giá trị bạn đã gặp.
Gợi ý 3
Dãy số rất nhanh chóng giảm xuống dưới vài trăm, nên tập hợp lưu trữ vẫn nhỏ.
Độ phức tạp mong đợi
thời gian O(log n) bước cho mỗi số, bộ nhớ phụ O(1) nếu dùng hai con trỏ
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.