What is the fastest way to find the number of perfect squares between two numbers?

Question

1.00/5 (2 votes)

See more:

I have used:

int(math.sqrt(last) - math.sqrt(first))

for getting the answer, whereas it is not working for some test-cases. So, can anyone suggest me a fast algorithm for the above question.

Posted 20-Mar-14 5:27am

Jalem Raj Rohit

Updated 17-Nov-22 13:19pm

v2

Add a Solution

Comments

joshrduncan2012 20-Mar-14 11:34am

Why isn't this working for some test cases?

Have you tried searching on google for something related to this?

YvesDaoust 31-Mar-14 5:31am

You do not specify if the first and last bounds are considered to be "between" as well.

3 solutions

Solution 3

The number of perfect squares between 0 and N (both inclusive), is the integer square root of N, let isqrt(N).

So the number of perfect squares between first and last (bounds inclusive), is the difference isqrt(last) - isqrt(first - 1).

The integer square root can be computed as the square root cast to int,

Python

int(math.sqrt(last)) - int(math.sqrt(first - 1))

Posted 30-Mar-14 23:36pm

YvesDaoust

Updated 30-Mar-14 23:41pm

v5

Add a Solution

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Pascal-78 · Accepted Answer · 2014-03-20T06:52:00

I think you need the number of integer between the first integer after sqrt(first) and before sqrt(last).

To get the first integer after, you can use Math.Ceiling.

To get the first integer before, you can use Math.Floor.

Then the complete formula should be :

C#

Math.Floor(Math.Sqrt(last)) - Math.Ceiling(Math.Sqrt(first)) + 1

+1 because if the first integer before last is the first integer after first, the difference will be 0 but you have 1 integer.

For example : with sqrt(first) = 2.3 and sqrt(last) = 3.2
you have 1 integer between the two numbers = 3 but Floor(3.2)=3 and Ceiling(2.3)=3
and Floor(3.2)-Ceiling(2.3) = 0.

This code is written using C#, but I'm sure you can found the floor and ceiling functions in other language.

Jalem Raj Rohit · Accepted Answer · 2014-03-20T06:57:00

Solution 2

Python

import math
N = int(input())

for i in range(0,N):
    first,last = map(int,input().split(" "))
    print(math.floor(math.sqrt(last)) - math.ceil(math.sqrt(first)) + 1)

Posted 20-Mar-14 6:57am

Jalem Raj Rohit

What is the fastest way to find the number of perfect squares between two numbers?

3 solutions

Solution 1

Solution 2

Solution 3

Add your solution here

Preview 0

What is the fastest way to find the number of perfect squares between two numbers?

3 solutions

Solution 1

Solution 2

Solution 3

Add your solution here

Preview 0

Existing Members

...or Join us