HPYNOS - Happy Numbers I

Xem đề bài trên SPOJ

Quá trình "tách rời" một số nguyên được miêu tả là quá trình tính tổng bình phương các chữ số của nó lại với nhau. Ví dụ, kết quả của quá trình "tách rời" số 125 là (1^2 + 2^2 + 5^2) = 30. Một số N được gọi là con số vui vẻ, nếu sau nhiều quá trình "tách rời" liên tiếp kết quả đạt thu cuối cùng bằng 1. Nếu kết quả không thể bằng 1 sau nhiêu quá trình "tách rời" liên tiếp, thì N không phải là con số vui vẻ.

Yêu cầu: Viết chương trình nhập vào số nguyên N, xác định xem nó có phải con số vui vẻ hay không.

Ràng buộc:

1 <= N <= 2147483647 (2^31 - 1).

Input: một và chỉ một số nguyên N.

Output: một dòng duy nhất chứa số nguyên T là số lần biến đổi số N để kết luận xem nó có phải con số vui vẻ hay không. Nếu N không phải con số vui vẻ, in ra -1.

Ví dụ:

Input:

19

Output:

4

Giải thích:

1. 19 => 1^2 + 9^2 = 82
2. 82 => 8^2 + 2^2 = 68
3. 68 => 6^2 + 8^2 = 100
4. 100 => 1^2 + 0^2 + 0^2 = 1 (dừng)

Input: 

204

Output

-1

Giải thích:

1. 204 => 2^2 + 0^2 + 4^2 = 20
2. 20 => 2^2 +0^2 = 4
3. 4 => 4^2 = 16
4. 16 => 1^2 + 6^2 = 37
5. 37 => 3^2 + 7^2 = 58
6. 58 => 5^2 + 8^2 = 89
7. 89 => 8^2 + 9^2 = 145
8. 145 => 1^2 + 4^2 + 5^2 = 42
9. 42 => 4^2 + 2^2 = 20 (tiếp tục lặp lại từ bước 2).

Solution: Chú ý là 2^31-1 vẫn nằm trong phạm vi của integer, hơn nữa công việc của chúng ta là xử lý bình phương của các chữ số, không phải cả số hạng nên kiểu dữ liệu toàn bài sử dụng integer vẫn AC bình thường. Dùng một mảng lưu lại những số sau khi xử lý, dùng một thuật toán tìm kiếm hiệu quả. Cuối cùng là duyệt trâu qua từng số hạng đã xử lý để đưa ra kết quả đề bài.

Code mẫu (C++, sử dụng hàm tìm kiếm nhị phân dựng sẵn)