ProblemGiven two integers a and b with 1 ≤ a ≤ b, count the perfect squares in…
2024
Problem
Given two integers a and b with 1 ≤ a ≤ b, count the perfect squares in the inclusive interval [a, b]. A perfect square is an integer of the form k2 for some non-negative integer k.
Input format
One line containing two space-separated integers a and b.
Output format
Print one integer: the number of perfect squares between a and b, inclusive.
Constraints
1 ≤ a ≤ b ≤ 100000
Sample 1
Input
3 8
Output
1Explanation: 4 is the only perfect square in [3, 8].
Sample 2
Input
9 25
Output
3Explanation: 9, 16, and 25 are the perfect squares in [9, 25].
Attempted by 1 students.
Show answer & explanation
Concept
A perfect square has the form k2. Therefore, squares inside [a, b] correspond exactly to integer roots k from ceil(√a) through floor(√b). The number of integers in an inclusive range [L, R] is max(0, R − L + 1).
Application
Compute the first and last integer roots whose squares remain inside the interval.
Read a and b.
Let L = floor(√a). If L2 < a, increase L by 1; now L = ceil(√a).
Let R = floor(√b).
Print max(0, R − L + 1).
Cross-check
For [3, 8], L = 2 and R = 2, so the count is 1.
For [9, 25], L = 3 and R = 5, so the count is 3.
Result and complexity
The algorithm uses O(1) time and O(1) extra space. Integer square-root correction avoids boundary errors from floating-point rounding.