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)\):

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
We've worked on this challenge in these gyms: modena 
comments powered by Disqus