Tất cả thử thách
Dễ 0 đã giải Tỷ lệ chấp nhận 0%

Số hạnh phúc (Happy number)

Xác định xem việc lặp lại phép tính tổng bình phương các chữ số có đưa một số về 1 hay không.

Bạn sẽ học được gì

  • Tính tổng bình phương các chữ số
  • Phát hiện dãy lặp lại bằng tập hợp (set) hoặc hai con trỏ
  • Dừng vòng lặp theo một trong hai điều kiện

Đề bài

Xem bản gốc (English)

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ụ

Ví dụ 1
Đầ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.

Ví dụ 2
Đầ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.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

Chưa có lời giải nào đạt. Giải bài này để giành hạng nhất.

Học hỏi từ người khác

Giải pháp cộng đồng

Chưa có giải pháp nào được chia sẻ. Hãy giải thử thách này để đăng giải pháp đầu tiên.