Рубрики

Проверьте идеальный квадрат, используя сложение / вычитание

Учитывая положительное целое число n, проверьте, является ли оно идеальным квадратом или нет, используя только операции сложения / вычитания с минимальной временной сложностью.

Мы настоятельно рекомендуем вам свернуть браузер и попробовать это в первую очередь.

Мы можем использовать свойство нечетного числа для этой цели:

Addition of first n odd numbers is always perfect square 
1 + 3 = 4,      
1 + 3 + 5 = 9,     
1 + 3 + 5 + 7 + 9 + 11 = 36 ...

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

C ++

// C ++ программа для проверки, является ли n идеальным квадратом
// или не
#include <bits/stdc++.h>

  

using namespace std;

  
// Эта функция возвращает true, если n
// идеальный квадрат, иначе ложь

bool isPerfectSquare(int n)

{

    // сумма - сумма всех нечетных чисел. я есть

    // использовал одно за другим нечетные числа

    for (int sum = 0, i = 1; sum < n; i += 2) {

        sum += i;

        if (sum == n)

            return true;

    }

    return false;

}

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

int main()

{

    isPerfectSquare(35) ? cout << "Yes\n" : cout << "No\n";

    isPerfectSquare(49) ? cout << "Yes\n" : cout << "No\n";

    return 0;

}

Джава

// Java-программа для проверки, если n
// идеально квадрат или нет

  

public class GFG {

  

    // Эта функция возвращает true, если n

    // идеальный квадрат, иначе ложь

    static boolean isPerfectSquare(int n)

    {

        // сумма - сумма всех нечетных чисел. я есть

        // использовал одно за другим нечетные числа

        for (int sum = 0, i = 1; sum < n; i += 2) {

            sum += i;

            if (sum == n)

                return true;

        }

        return false;

    }

  

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

    public static void main(String args[])

    {

  

        if (isPerfectSquare(35))

            System.out.println("Yes");

        else

            System.out.println("NO");

  

        if (isPerfectSquare(49))

            System.out.println("Yes");

        else

            System.out.println("No");

    }

}

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

python3

# Эта функция возвращает true, если n
# идеальный квадрат, иначе ложь

def isPerfectSquare(n):

  

    # the_sum - сумма всех нечетных чисел. я есть

    # использовал один за другим нечетные числа

    i = 1

    the_sum = 0

    while the_sum < n:

        the_sum += i

        if the_sum == n:

            return True

        i += 2

    return False

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

if __name__ == "__main__":

    print('Yes') if isPerfectSquare(35) else print('NO')

    print('Yes') if isPerfectSquare(49) else print('NO')

  
# Этот код работает только в Python 3

C #

// C # программа для проверки, если n
// идеально квадрат или нет

using System;

  

public class GFG {

  

    // Эта функция возвращает true, если n

    // идеальный квадрат, иначе ложь

    static bool isPerfectSquare(int n)

    {

        // сумма - сумма всех нечетных чисел. я есть

        // использовал одно за другим нечетные числа

        for (int sum = 0, i = 1; sum < n; i += 2) {

            sum += i;

            if (sum == n)

                return true;

        }

        return false;

    }

  

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

    public static void Main(String[] args)

    {

  

        if (isPerfectSquare(35))

            Console.WriteLine("Yes");

        else

            Console.WriteLine("No");

  

        if (isPerfectSquare(49))

            Console.WriteLine("Yes");

        else

            Console.WriteLine("No");

    }

}

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

PHP

<?php
// PHP программа для проверки, если n
// идеальный квадрат или нет

  
// Эта функция возвращает true, если n
// идеальный квадрат, иначе ложь

function isPerfectSquare($n)

{

    // сумма - сумма всех нечетных чисел.

    // меня используют один за другим, держат нечетным

    // числа

    for ( $sum = 0, $i = 1; $sum < $n;

                              $i += 2)

    {

        $sum += $i;

        if ($sum == $n)

            return true;

    }

      

    return false;

}

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

if(isPerfectSquare(35))

    echo "Yes\n";

else

    echo "No\n";

      

if(isPerfectSquare(49))

    echo "Yes\n";

else

    echo "No\n";

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


Выход :

No
Yes

Как это работает?
Ниже приведено объяснение вышеуказанного подхода.

1 + 3 + 5 + ...  (2n-1) = &Sum;(2*i - 1) where 1<=i<=n
                        = 2*&Sum;i - &Sum;1  where 1<=i<=n
                        = 2n(n+1)/2 - n
                        = n(n+1) - n
                        = n2

Ссылка:
http://espressocode.top/sum-first-n-odd-numbers-o1-complexity/
http://blog.jgc.org/2008/02/sum-of-first-n-odd-numbers-is-always.html

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

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

Проверьте идеальный квадрат, используя сложение / вычитание

0.00 (0%) 0 votes