Рубрики

Наибольшее число, которое не является идеальным квадратом

Учитывая n целых чисел, найти наибольшее число не является идеальным квадратом. Выведите -1, если не существует числа, которое является идеальным квадратом.

Примеры:

Input : arr[] = {16, 20, 25, 2, 3, 10| 
Output : 20 
Explanation: 20 is the largest number 
that is not a perfect square 

Input : arr[] = {36, 64, 10, 16, 29, 25| 
Output : 29 

Нормальным решением является сортировка элементов, сортировка n чисел и начало проверки на предмет неидеального квадратного числа с помощью функции sqrt (). Первое число с конца, которое не является идеальным квадратным числом, является нашим ответом. Сложность сортировки — O (n log n), а функции sqrt () — log n, поэтому в худшем случае сложность O (n log n log n).

Эффективным решением является итерация для всех элементов с использованием обхода в O (n), сравнение каждый раз с максимальным элементом и сохранение максимума всех неидеальных квадратов. Число, сохраненное в максимуме, будет нашим ответом.

Ниже приведена иллюстрация вышеупомянутого подхода:

CPP

// Программа CPP, чтобы найти самый большой не идеальный
// квадратное число среди n чисел
#include <bits/stdc++.h>

using namespace std;

bool check(int n)

{

    // берет квадрат числа

    int d = sqrt(n);

  

    // проверяет, является ли это идеальное квадратное число

    if (d * d == n)

        return true;

  

    return false;

}

  
// функция, чтобы найти наибольшее не совершенное квадратное число

int largestNonPerfectSquareNumber(int a[], int n)

{

    // хранит максимум всех не совершенных квадратных чисел

    int maxi = -1;

  

    // пройти для всех элементов в массиве

    for (int i = 0; i < n; i++) {

  

        // сохранить максимум, если не идеальный квадрат

        if (!check(a[i]))

            maxi = max(a[i], maxi);

    }

    return maxi;

}

  
// код драйвера для проверки вышеуказанных функций

int main()

{

    int a[] = { 16, 20, 25, 2, 3, 10 };

  

    int n = sizeof(a) / sizeof(a[0]);

    // вызов функции

    cout << largestNonPerfectSquareNumber(a, n);

    return 0;

}

Джава

// Java-программа для поиска
// самый большой не идеальный
// квадратное число среди n чисел

  

import java.io.*;

   

class GfG{

       

static Boolean check(int n)

{

    // берет квадрат числа

    int d = (int)Math.sqrt(n);

   

    // проверяет, является ли это идеальное квадратное число

    if (d * d == n)

        return true;

   

    return false;

}

   
// функция найти самый большой
// неидеальное квадратное число

static int largestNonPerfectSquareNumber(int a[], int n)

{

    // хранит максимум всего

    // неидеальные квадратные числа

    int maxi = -1;

   

    // пройти для всех элементов в массиве

    for (int i = 0; i < n; i++) {

   

        // сохранить максимум, если

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

        if (!check(a[i]))

            maxi = Math.max(a[i], maxi);

    }

    return maxi;

}

  

    public static void main (String[] args) {

  

        int a[] = { 16, 20, 25, 2, 3, 10 };

        int n = a.length;

  

        // вызов функции

        System.out.println(largestNonPerfectSquareNumber(a, n));

    }

}

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

python3

# Python программа для поиска
# самый большой не идеальный
# квадратное число среди n чисел

  

import math

def check( n):

  

    # принимает квадрат числа

    d = int(math.sqrt(n))

   

    # проверяет, является ли это

    # идеальное квадратное число

    if (d * d == n):

        return True

   

    return False

  

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

def largestNonPerfectSquareNumber(a, n):

  

    # хранит максимум всего

    # неидеальные квадратные числа

    maxi = -1

   

    # ход для всех элементов

    # в массиве

    for i in range(0,n):

   

        # сохранить максимум, если

        # не идеальный квадрат

        if (check(a[i])==False):

            maxi = max(a[i], maxi)

      

    return maxi

  
# код водителя

a = [ 16, 20, 25, 2, 3, 10 ]

n= len(a)

  
# вызов функции

print (largestNonPerfectSquareNumber(a, n))

  
# Этот код предоставлен Gitanjali.

C #

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

using System;

  

class GfG {

      

    static bool check(int n)

    {

          

        // берет квадрат числа

        int d = (int)Math.Sqrt(n);

      

        // проверяет, является ли это идеальным

        // квадратное число

        if (d * d == n)

            return true;

      

        return false;

    }

      

    // функция найти самый большой

    // неидеальное квадратное число

    static int largestNonPerfectSquareNumber(

                               int []a, int n)

    {

          

        // хранит максимум всего

        // неидеальные квадратные числа

        int maxi = -1;

      

        // пройти все элементы в

        // массив

        for (int i = 0; i < n; i++) {

      

            // сохранить максимум, если

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

            if (!check(a[i]))

                maxi = Math.Max(a[i], maxi);

        }

          

        return maxi;

    }

  

    // код драйвера для проверки вышеуказанных функций

    public static void Main ()

    {

  

        int []a = { 16, 20, 25, 2, 3, 10 };

        int n = a.Length;

  

        // вызов функции

        Console.WriteLine(

           largestNonPerfectSquareNumber(a, n));

    }

}

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

PHP

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

  

function check($n)

{

      

    // занимает площадь

    // числа

    $d = sqrt($n);

  

    // проверяет, является ли это

    // идеальное квадратное число

    if ($d * $d == $n)

        return true;

  

    return false;

}

  
// функция для поиска наибольшего
// неидеальное квадратное число

function largestNonPerfectSquareNumber($a, $n)

{

      

    // хранит максимум

    // все не идеальный квадрат

    // числа

    $maxi = -1;

  

    // пройти для всех

    // элементы в массиве

    for ($i = 0; $i < $n; $i++)

    {

  

        // сохранить максимум, если

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

        if (!check($a[$i]))

            $maxi = max($a[$i], $maxi);

    }

    return $maxi;

}

  

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

    $a = array(16, 20, 25, 2, 3, 10);

    $n = count($a);

      

    // вызов функции

    echo largestNonPerfectSquareNumber($a, $n);

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


Выход:

20

Сложность времени можно рассматривать как O (N) в качестве SQRT () функция может быть реализована в O (1) времени для фиксированного размера (32 бит или 64 бит) числа [См Wiki для подробностей]

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

Наибольшее число, которое не является идеальным квадратом

0.00 (0%) 0 votes