Đề bài
Căn bậc hai nguyên của n là căn bậc hai làm tròn xuống, tức là số nguyên r lớn nhất thỏa mãn r × r ≤ n. Hàm căn bậc hai trong thư viện tính bằng số thực dấu phẩy động (floating point), nên với số lớn kết quả có thể lệch đi 1. Vì vậy bạn hãy chỉ dùng số nguyên, chẳng hạn tìm kiếm nhị phân (binary search) trên khoảng các đáp án có thể.
Hãy viết integer_square_root(n).
Đầu vào
n: Một số nguyên không âm.
Đầu ra
Trả về số nguyên r lớn nhất sao cho r × r ≤ n.
Ràng buộc
0 ≤ n ≤ 10^18
Ví dụ
Đầu vào:
n = 50
Kết quả mong đợi:
expected = 7
Đầu vào:
long long n = 50;
Kết quả mong đợi:
long long expected = 7;
Đầu vào:
long n = 50;
Kết quả mong đợi:
long expected = 7;
Giải thích
7 × 7 = 49 ≤ 50 nhưng 8 × 8 = 64 > 50, nên đáp án là 7.
Đầu vào:
n = 144
Kết quả mong đợi:
expected = 12
Đầu vào:
long long n = 144;
Kết quả mong đợi:
long long expected = 12;
Đầu vào:
long n = 144;
Kết quả mong đợi:
long expected = 12;
Giải thích
144 đúng bằng 12 × 12, nên đáp án là 12.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Đáp án nằm giữa 0 và n, và r × r tăng khi r tăng, nên mỗi bước bạn có thể chia đôi khoảng tìm kiếm.
Gợi ý 2
Với n lớn, r × r có thể bị tràn số; hãy so sánh r với n / r, hoặc giới hạn cận trên.
Gợi ý 3
Tự kiểm tra bằng tay các đầu vào nhỏ như 0, 1 và 3.
Độ phức tạp mong đợi
thời gian O(log n), bộ nhớ phụ O(1)
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.