Number of perfect squares between two given numbers

Try it on GfG Practice

Given two numbers a and b where 1<=a<=b, find the number of perfect squares between a and b (a and b inclusive).

Example

Input: a = 3, b = 8
Output: 1
Explanation: The only perfect square in given range is 4.

Input: a = 9, b = 25
Output: 3
Explanation: The three perfect squares in given range are 9, 16 and 25

[Naive Approach] - One by One Counting

The idea for this approach is to use a loop to iterate from a to b and count the numbers that are perfect squares.

#include <bits/stdc++.h>
using namespace std;

int countSquares(int a, int b)
{   
    int cnt = 0;
    
    // Traverse through all numbers
    for (int i = a; i <= b; i++)
    
        // Check if current number 'i' 
        // is perfect square
        for (int j = 1; j * j <= i; j++)
            if (j * j == i)
                cnt++;

    return cnt;
}

int main()
{
    int a = 9, b = 25;
    cout <<countSquares(a, b);
    return 0;
}

class CountSquares {

    static int countSquares(int a, int b)
    {   
        int cnt = 0;
        
        // Traverse through all numbers
        for (int i = a; i <= b; i++)
        
            // Check if current number 'i' is perfect
            // square
            for (int j = 1; j * j <= i; j++)
                if (j * j == i)
                    cnt++;
        return cnt;
    }
}
public class PerfectSquares {
    public static void main(String[] args)
    {
        int a = 9, b = 25;
        CountSquares obj = new CountSquares();
        System.out.print(obj.countSquares(a, b));
    }
}

def CountSquares(a, b):

    cnt = 0 
    
    # Traverse through all numbers
    for i in range (a, b + 1):
        j = 1;
        while j * j <= i:
            if j * j == i:
                 cnt = cnt + 1
            j = j + 1
        i = i + 1
    return cnt

a = 9
b = 25
print (CountSquares(a, b))

using System;
class GFG {

    // Function to count squares
    static int countSquares(int a, int b)
    {
        int cnt = 0;
        
        // Traverse through all numbers
        for (int i = a; i <= b; i++)
        
            // Check if current number
            // 'i' is perfect square
            for (int j = 1; j * j <= i; j++)
                if (j * j == i)
                    cnt++;
        return cnt;
    }
    public static void Main()
    {
        int a = 9, b = 25;
        Console.Write(countSquares(a, b));
    }
}

function countSquares(a, b)
{
    let cnt = 0;

    // Traverse through all numbers
    for (let i = a; i <= b; i++)

        // Check if current number
        // 'i' is perfect square
        for (let j = 1; j * j <= i; j++)
            if (j * j == i)
                cnt++;

    return cnt;
}

let a = 9;
let b = 25;
console.log(countSquares(a, b));

Count of squares is 3

Time Complexity: O((b-a) * sqrt(b)).
Auxiliary Space: O(1)

[Expected Approach] - Using Square Roots of a and b

The idea for this approach is to simply take square root of ‘a’ and ‘b’ and count the numbers between them by using this formula floor(sqrt(b)) - ceil(sqrt(a)) + 1
We take floor of sqrt(b) because we need to consider numbers before b.
We take ceil of sqrt(a) because we need to consider numbers after a.

Example: b = 24, a = 8.
floor(sqrt(b)) = 4, ceil(sqrt(a)) = 3.
And number of squares is 4 - 3 + 1 = 2.(9 and 16) .

#include <bits/stdc++.h>
using namespace std;

int countSquares(int a, int b)
{
    return (floor(sqrt(b)) - ceil(sqrt(a)) + 1);
}

int main()
{
    int a = 9, b = 25;
    cout <<countSquares(a, b);
    return 0;
}

class CountSquares {
    double countSquares(int a, int b)
    {
        return (Math.floor(Math.sqrt(b)) - Math.ceil(Math.sqrt(a)) + 1);
    }
}

public class PerfectSquares {
    public static void main(String[] args)
    {
        int a = 9, b = 25;
        CountSquares obj = new CountSquares();
        System.out.print((int)obj.countSquares(a, b));
    }
}

import math
def CountSquares(a, b):
    return (math.floor(math.sqrt(b)) - math.ceil(math.sqrt(a)) + 1)

a = 9
b = 25
print (int(CountSquares(a, b)))

using System;
class GFG {

    static double countSquares(int a, int b)
    {
        return (Math.Floor(Math.Sqrt(b)) - Math.Ceiling(Math.Sqrt(a)) + 1);
    }

    public static void Main()
    {
        int a = 9, b = 25;
        Console.Write((int)countSquares(a, b));
    }
}

function countSquares(a, b)
{
   return (Math.floor(Math.sqrt(b)) -  Math.ceil(Math.sqrt(a)) + 1);
}


    let a = 9; 
    let b = 25;
    console.log(countSquares(a, b));

Count of squares is 3

Time Complexity: O(log b) as any typical implementation of square root for a number n takes time equal to O(Log n)
Auxiliary Space: O(1)