See the original problem on HackerRank.
Solutions
The naive solution runs in timeout.
A better solution is \(O(\sqrt{B})\):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
inline pair<bool, int> IsPerfectSquare(int n)
{
const auto root = sqrt(n);
return make_pair(root == floor(root), root);
}
int main()
{
size_t T; cin >> T;
int a, b;
while (T--)
{
cin >> a >> b;
pair<bool, int> pfs = {false, 0};
while (a<=b && !(pfs=IsPerfectSquare(a)).first)
++a;
unsigned int count = pfs.first;
auto root = pfs.second+1;
while (a = root*root, a<=b)
{
++root; ++count;
}
cout << count << endl;
}
}
|
The best solution is \(O(1)\):
Python:
1
2
3
4
5
6
7
|
from math import *
t = input()
for _ in range(t):
a, b = map(int, raw_input().split())
a = ceil(sqrt(a))
b = floor(sqrt(b))
print int(b-a) + 1
|
Haskell:
1
2
3
4
5
6
7
8
9
|
sherlockAndSquares :: [Double] -> Int
sherlockAndSquares [a, b] = b' - a' + 1
where
a' = ceiling . sqrt $ a
b' = floor . sqrt $ b
main =
interact $
unlines . fmap (show . sherlockAndSquares . fmap read . words) . tail . lines
|
Pay attention to precision errors: this works with Double but one test
fails using Float.