Dễ 0 đã giải Tỷ lệ chấp nhận 0%

Căn bậc hai nguyên

Tìm số nguyên lớn nhất có bình phương không vượt quá n mà không dùng hàm căn bậc hai.

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

  • Tìm đáp án trong một khoảng bằng tìm kiếm nhị phân
  • So sánh r × r với n mà không bị tràn số
  • Tránh lỗi làm tròn của số thực dấu phẩy động

Đề bài

Xem bản gốc (English)

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ụ

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

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

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.