Sherlock and Squares

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.

We've worked on this challenge in these gyms: modena  milan 
comments powered by Disqus