Рубрики

Количество идеальных квадратов между двумя заданными числами

Для двух заданных чисел a и b, где 1 <= a <= b, найдите число идеальных квадратов между a и b (a и b включительно).

Примеры

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

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

Метод 1 : Один наивный подход заключается в проверке всех чисел между a и b (включая a и b) и увеличении числа на единицу, когда мы встречаем идеальный квадрат.

Ниже приведена реализация вышеуказанной идеи:

C ++

// Простой метод для подсчета квадратов между a и b
#include <bits/stdc++.h>

using namespace std;

  

int countSquares(int a, int b)

{

    int cnt = 0; // Инициализировать результат

  

    // Обход всех номеров

    for (int i = a; i <= b; i++)

  

        // Проверяем, является ли текущий номер 'i' идеальным

        // площадь

        for (int j = 1; j * j <= i; j++)

            if (j * j == i)

                cnt++;

  

    return cnt;

}

  
// Код драйвера

int main()

{

    int a = 9, b = 25;

    cout << "Count of squares is "

         << countSquares(a, b);

    return 0;

}

Джава

// Java-программа для подсчета квадратов между a и b

class CountSquares {

  

    static int countSquares(int a, int b)

    {

        int cnt = 0; // Инициализировать результат

  

        // Обход всех номеров

        for (int i = a; i <= b; i++)

  

            // Проверяем, является ли текущий номер 'i' идеальным

            // площадь

            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("Count of squares is " + obj.countSquares(a, b));

    }

}

питон

# Программа Python для подсчета квадратов между a и b

  

def CountSquares(a, b):

  

    cnt = 0 # инициализировать результат

  

    # Пройдите через все числа

    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 "Count of squares is:", CountSquares(a, b)

C #

// C # программа для подсчета квадратов
// между а и б

using System;

  

class GFG {

  

    // Функция для подсчета квадратов

    static int countSquares(int a, int b)

    {

        // Инициализировать результат

        int cnt = 0;

  

        // Обход всех номеров

        for (int i = a; i <= b; i++)

  

            // Проверяем текущий номер

            // 'i' - идеальный квадрат

            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("Count of squares is " + countSquares(a, b));

    }

}

  
// Этот код предоставлен Sam007

PHP

<?php
// Простой метод для подсчета квадратов
// между а и б

  

function countSquares($a, $b)

{

    $cnt = 0; // Инициализировать результат

  

    // Обход всех номеров

    for ($i = $a; $i <= $b; $i++)

  

        // Проверяем текущий номер

        // 'i' - идеальный квадрат

        for ($j = 1; $j * $j <= $i;

                              $j++)

            if ($j * $j == $i)

                $cnt++;

  

    return $cnt;

}

  
// Код драйвера

  

    $a = 9; $b = 25;

    echo "Count of squares is ".

              countSquares($a, $b);

  
// Этот код предоставлен ajit.
?>

Выход :

Count of squares is 3

Верхняя граница времени Сложность этого решения O ((ba) * sqrt (b)).

Метод 2 (эффективный) Мы можем просто взять квадратный корень из «а» и квадратный корень из «b» и посчитать идеальные квадраты между ними, используя

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.


For example, let b = 24, a = 8.  floor(sqrt(b)) = 4, 
ceil(sqrt(a)) = 3.  And number of squares is 4 - 3 + 1
= 2. The two numbers are 9 and 16.

Ниже приведена реализация вышеуказанной идеи:

C ++

// Эффективный метод для подсчета квадратов между a и b
#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 << "Count of squares is "

         << 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("Count of squares is " + (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 "Count of squares is:", int(CountSquares(a, b))

C #

// C # программа для эффективного метода
// посчитать квадраты между 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("Count of squares is " + (int)countSquares(a, b));

    }

}

  
// Этот код предоставлен Sam007.

PHP

<?php
// Эффективный код PHP для подсчета
// квадраты между a и b

  
// Метод подсчета квадрата
// между а и б

function countSquares($a, $b)

{

    return (floor(sqrt($b)) - 

            ceil(sqrt($a)) + 1);

}

  
// Код драйвера
{

    $a = 9;

    $b = 25;

    echo "Count of squares is "

           countSquares($a, $b);

    return 0;

}
// Этот код предоставлен нитин митталь.
?>


Выход :

Count of squares is 3

Временная сложность этого решения составляет O (Log b). Типичная реализация квадратного корня для числа n занимает время, равное O (Log n) [См. Это для примера реализации квадратного корня]

Эта статья предоставлена Рахул Аггарвал . Если вам нравится GeeksforGeeks и вы хотите внести свой вклад, вы также можете написать статью и отправить ее по почте на contrib@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Количество идеальных квадратов между двумя заданными числами

0.00 (0%) 0 votes