Perfect Square Count Solution - Competitive Programming

Today when I was practicing problem-solving questions in hackerrank platform, I came across this interesting question, I thought I should share with all of you.

Have you ever wonder, Is there any pattern through which a perfect square integer came across our way?

For example, Let's take numbers within the range from 1 to 10, we have,

1, 2, 3, 4, 5, 6, 7, 8, 9, 10.

There exist 1,4,9 perfect squares in between the numbers 1 to 10. Do you notice any pattern or relation between these perfect squares? Can we find a pattern or formula by which we can get the next perfect square?

Let's understand this bit by bit, We know that 1 is always a perfect square. Now, I want to find the next perfect square after 1. The trick is simple. I will do :

1 + squareRoot(1)*2 + 1 =  4.

Amazing haan. Let's continue and find the next perfect square after 4. we have to do...

4 + squareRoot(4)*2 + 1 =  9

that's really amazing! Should we continue? Let's find the next perfect square integer after 9, easy.

-> 9 + squareRoot(9)*2 + 1
-> 9+6+1 = 16.

Similarly, The next perfect square will be,

16 + squareRoot(16)*2+1
16+8+1 = 25.

Now, Let's come back to our question, Write a program to find the number of perfect square integers between a given range. I will be writing the code in python.

So, let's say I want to find the number of perfect square integers between 24 to 50.

First, we need to check whether the starting digit is a perfect square or not. The reason behind we are checking is, if the starting digit is a perfect square, then we can use the above-discussed pattern to jump over the next perfect square and by doing so we can optimize our iteration so that we do not have to iterate over each number in between the given range.

In our example, the starting digit is 24. we first check whether it is a perfect square or not. Just import the math module in python and call the sqrt function to do so.

```python
import math
```


```python
math.sqrt(24)
```




    4.898979485566356



Here the output is a decimal digit. So 24 is not a perfect square. What I will do now is I will use the str() function to make this result as string, and will check if the last two character are '.0' or not, because if the number is a perfect square then it will look something like this:


```python
math.sqrt(36)
```




    6.0



Simple and neat haan! So Let's write our program.


```python
a = 24
b = 50
count = 0
while a<=b:
    
    if str(math.sqrt(a))[-2:] != '.0':
        a = a+1
    else:
        
        count = count+1
        a = a + (2*math.sqrt(a))+1
print("There are",count,"perfect squares exist in between the provided range!!!")
```

    There are 3 perfect squares exist in between the provided range!!!


Hence, Our code is working fine. We don't need to iterate over every element. we are just jumping over perfect squares because we know the pattern between them.

That's quite clean and neat.

If you want you can print those perfect squares. For that we need to just tweak a lil bit.


```python
a = 24
b = 50
count = 0
while a<=b:
    
    if str(math.sqrt(a))[-2:] != '.0':
        a = a+1
    else:
        print(a)
        count = count+1
        a = a + (2*math.sqrt(a))+1
print("There are",count,"perfect squares exist in between the provided range!!!")
```

    25
    36.0
    49.0
    There are 3 perfect squares exist in between the provided range!!!


So, I hope you enjoyed the relationship between perfect square integers. It was fun doing this. For now, Thankyou and Peace Out.


```python

```