Short Problem Definition:
Watson gives two integers A & B to Sherlock and asks if he can count the number of square integers between A and B (both inclusive).
A square integer is an integer which is the square of any integer. For example, 1, 4, 9, 16 are some of the square integers as they are squares of 1, 2, 3, 4 respectively.
time complexity is O(sqrt(N));
space complexity is O(1)
Just compute the difference between the square of the low end and the high end.
#!/usr/bin/py from math import * if __name__ == '__main__': 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
If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.