# 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 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 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 

 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.