Given n integers, find the largest number is not a perfect square. Print -1 if there is no number that is perfect square.
Examples:
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
A normal solution is to sort the elements and sort the n numbers and start checking from the back for a non-perfect square number using sqrt() function. The first number from the end which is not a perfect square number is our answer. The complexity of sorting is O(n log n) and of sqrt() function is log n, so in the worst case the complexity is O(n log n log n).
The efficient solution is to iterate for all the elements using traversal in O(n) and compare every time with the maximum element and store the maximum of all non-perfect squares. The number stored in maximum will be our answer.
Below is the illustration of the above approach:
CPP
// CPP program to find the largest non perfect // square number among n numbers#include <bits/stdc++.h>using namespace std;bool check(int n){ // takes the sqrt of the number int d = sqrt(n); // checks if it is a perfect square number if (d * d == n) return true; return false;}// function to find the largest non perfect square numberint largestNonPerfectSquareNumber(int a[], int n){ // stores the maximum of all non perfect square numbers int maxi = -1; // traverse for all elements in the array for (int i = 0; i < n; i++) { // store the maximum if not a perfect square if (!check(a[i])) maxi = max(a[i], maxi); } return maxi;}// driver code to check the above functionsint main(){ int a[] = { 16, 20, 25, 2, 3, 10 }; int n = sizeof(a) / sizeof(a[0]); // function call cout << largestNonPerfectSquareNumber(a, n); return 0;} |
Java
// Java program to find the// largest non perfect // square number among n numbersimport java.io.*; class GfG{ static Boolean check(int n){ // takes the sqrt of the number int d = (int)Math.sqrt(n); // checks if it is a perfect square number if (d * d == n) return true; return false;} // function to find the largest// non perfect square numberstatic int largestNonPerfectSquareNumber(int a[], int n){ // stores the maximum of all // non perfect square numbers int maxi = -1; // traverse for all elements in the array for (int i = 0; i < n; i++) { // store the maximum if // not a perfect square 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; // function call System.out.println(largestNonPerfectSquareNumber(a, n)); }}// This code is contributed by Gitanjali. |
Python3
# python program to find# the largest non perfect # square number among n numbersimport mathdef check( n): # takes the sqrt of the number d = int(math.sqrt(n)) # checks if it is a # perfect square number if (d * d == n): return True return False # function to find the largest# non perfect square numberdef largestNonPerfectSquareNumber(a, n): # stores the maximum of all # non perfect square numbers maxi = -1 # traverse for all elements # in the array for i in range(0,n): # store the maximum if # not a perfect square if (check(a[i])==False): maxi = max(a[i], maxi) return maxi# driver codea = [ 16, 20, 25, 2, 3, 10 ]n= len(a)# function callprint (largestNonPerfectSquareNumber(a, n))# This code is contributed by Gitanjali. |
C#
// C# program to find the largest non perfect // square number among n numbersusing System;class GfG { static bool check(int n) { // takes the sqrt of the number int d = (int)Math.Sqrt(n); // checks if it is a perfect // square number if (d * d == n) return true; return false; } // function to find the largest // non perfect square number static int largestNonPerfectSquareNumber( int []a, int n) { // stores the maximum of all // non perfect square numbers int maxi = -1; // traverse for all elements in // the array for (int i = 0; i < n; i++) { // store the maximum if // not a perfect square if (!check(a[i])) maxi = Math.Max(a[i], maxi); } return maxi; } // driver code to check the above functions public static void Main () { int []a = { 16, 20, 25, 2, 3, 10 }; int n = a.Length; // function call Console.WriteLine( largestNonPerfectSquareNumber(a, n)); }}// This code is contributed by vt_m. |
Javascript
<script>// JavaScript program to find the// largest non perfect // square number among n numbersfunction check(n){ // takes the sqrt of the number let d = Math.sqrt(n); // checks if it is a perfect square number if (d * d == n) return true; return false;} // function to find the largest// non perfect square numberfunction largestNonPerfectSquareNumber(a, n){ // stores the maximum of all // non perfect square numbers let maxi = -1; // traverse for all elements in the array for (let i = 0; i < n; i++) { // store the maximum if // not a perfect square if (!check(a[i])) maxi = Math.max(a[i], maxi); } return maxi;} // Driver Code let a = [ 16, 20, 25, 2, 3, 10 ]; let n = a.length; // function call document.write(largestNonPerfectSquareNumber(a, n)); </script> |
PHP
<?php// PHP program to find // the largest non perfect // square number among n // numbersfunction check($n){ // takes the sqrt // of the number $d = sqrt($n); // checks if it is a // perfect square number if ($d * $d == $n) return true; return false;}// function to find the largest// non perfect square numberfunction largestNonPerfectSquareNumber($a, $n){ // stores the maximum of // all non perfect square // numbers $maxi = -1; // traverse for all // elements in the array for ($i = 0; $i < $n; $i++) { // store the maximum if // not a perfect square if (!check($a[$i])) $maxi = max($a[$i], $maxi); } return $maxi;} // Driver Code $a = array(16, 20, 25, 2, 3, 10); $n = count($a); // function call echo largestNonPerfectSquareNumber($a, $n);// This code is contributed by anuj_67.?> |
20
Time complexity can be considered as O(n) as sqrt() function can be implemented in O(1) time for fixed size (32 bit or 64 bit) integers
Approach#2: Using set()
This approach involves two iterations through the input array “arr”. In the first iteration, we determine all the perfect squares in the array and store them in a set. In the second iteration, we find the maximum number in the array that is not a perfect square. We accomplish this by checking each number in the array and updating the maximum number if the number is not a perfect square and is greater than the current maximum number.
Algorithm
- Define a function named “is_perfect_square” that takes an integer “n” as input and returns True if “n” is a perfect square, otherwise returns False. Also define a function named “largest_non_perfect_square” that takes a list of integers “arr” as input and returns the largest number in “arr” that is not a perfect square.
- Initialize an empty set called “perfect_squares”.
- Iterate through “arr” and for each number:
- Check if it is a perfect square using the “is_perfect_square” function.
- If it is a perfect square, add it to the “perfect_squares” set.
- Initialize a variable called “max_num” to -1.
- terate through “arr” again and for each number:
- Check if it is greater than “max_num” and not in the “perfect_squares” set.
- If it is, update “max_num” to be the current number.
- Return “max_num”.
C++
#include <bits/stdc++.h>using namespace std;// Function to check if a number is a perfect squarebool is_perfect_square(int n) { int root = sqrt(n); return root * root == n;}// Function to find the largest non-perfect square in the arrayint largest_non_perfect_square(const vector<int>& arr) { unordered_set<int> perfect_squares; // Find all perfect squares in the array and store them in a set for efficient lookup for (int num : arr) { if (is_perfect_square(num)) { perfect_squares.insert(num); } } int max_num = -1; // Iterate through the array to find the largest number that is not a perfect square for (int num : arr) { if (num > max_num && perfect_squares.find(num) == perfect_squares.end()) { max_num = num; } } return max_num;}int main() { vector<int> arr = {16, 20, 25, 2, 3, 10}; // Find the largest non-perfect square in the array and output the result cout <<largest_non_perfect_square(arr) << endl; return 0;}// THIS CODE IS CONTRIBUTED BY KIRTI AGARWAL |
Java
import java.util.HashSet;public class Main { // Function to check if a number is a perfect square static boolean isPerfectSquare(int n) { int root = (int) Math.sqrt(n); return root * root == n; } // Function to find the largest non-perfect square in the array static int largestNonPerfectSquare(int[] arr) { HashSet<Integer> perfectSquares = new HashSet<>(); // Find all perfect squares in the array and store them in a set for efficient lookup for (int num : arr) { if (isPerfectSquare(num)) { perfectSquares.add(num); } } int maxNum = -1; // Iterate through the array to find the largest number that is not a perfect square for (int num : arr) { if (num > maxNum && !perfectSquares.contains(num)) { maxNum = num; } } return maxNum; } public static void main(String[] args) { int[] arr = {16, 20, 25, 2, 3, 10}; // Find the largest non-perfect square in the array and output the result System.out.println(largestNonPerfectSquare(arr)); }} |
Python3
import mathdef is_perfect_square(n): return math.sqrt(n)**2 == ndef largest_non_perfect_square(arr): perfect_squares = set() for num in arr: if is_perfect_square(num): perfect_squares.add(num) max_num = -1 for num in arr: if num > max_num and num not in perfect_squares: max_num = num return max_numarr = [16, 20, 25, 2, 3, 10]print(largest_non_perfect_square(arr)) |
Javascript
function is_perfect_square(n) { // Check if the square root of n squared is equal to n return Math.sqrt(n) ** 2 == n;}function largest_non_perfect_square(arr) { // Create a set to store perfect squares let perfect_squares = new Set(); for (let num of arr) { if (is_perfect_square(num)) { perfect_squares.add(num); } } // Find the largest non-perfect square in the array let max_num = -1; for (let num of arr) { if (num > max_num && !perfect_squares.has(num)) { max_num = num; } } return max_num;}let arr = [16, 20, 25, 2, 3, 10];console.log(largest_non_perfect_square(arr)); |
20
Time complexity: The time complexity of this approach is O(n), where “n” is the length of the input array “arr”. This is because we iterate through the array twice, once to find the perfect squares and once to find the largest non-perfect square.
Auxiliary Space: The space complexity of this approach is O(sqrt(max(arr))), where “max(arr)” is the maximum value in the input array “arr”. This is because we create a set to store the perfect squares, and the maximum number of perfect squares in the range 0 to “max(arr)” is sqrt(max(arr)).
METHOD 3:Using sqrt function
The given problem is to find the largest number that is not a perfect square in the given list of integers. We iterate through the list and check whether the square root of each number is a whole number or not. If it is not, we compare the current number with the current largest non-perfect square number found so far and update the largest accordingly.
Algorithm:
- Initialize a variable named largest with -1.
- Iterate through the given list of integers arr.
- For each number, check whether its square root is a whole number or not using the modulus operator %. If the square root is not a whole number, i.e., the number is not a perfect square, and the number is greater than the current largest non-perfect square number found so far, update the largest variable with the current number.
- Return the largest variable.
Python3
from math import sqrtdef largest_non_perfect_square(arr): largest = -1 for num in arr: if sqrt(num) % 1 != 0 and num > largest: largest = num return largest# Example usage:arr = [16, 20, 25, 2, 3, 10]print(largest_non_perfect_square(arr)) # Output: 20 |
20
Time Complexity: The algorithm iterates through the entire list once. The square root calculation of each number takes constant time. Therefore, the time complexity of the algorithm is O(n).
Space Complexity: The algorithm uses only a constant amount of extra space to store the largest variable. Therefore, the space complexity of the algorithm is O(1).
METHOD 4:Using re
The given problem is to find the largest number in a given array that is not a perfect square.
Algorithm:
- Define a regular expression pattern to find perfect squares.
- Use the re module to find all perfect squares in the given array using the defined pattern.
- Sort the list of perfect squares in descending order.
- Iterate through the given array and return the first element that is not a perfect square.
Python3
import rearr = [16, 20, 25, 2, 3, 10]# regular expression pattern to find perfect squarespattern = r'\b[1-9][0-9]*\b'# find all perfect squares in the arrayperfect_squares = [int(num) for num in re.findall( pattern, ' '.join(map(str, arr))) if int(num)**0.5 % 1 == 0]# sort the array in descending orderperfect_squares.sort(reverse=True)# find the largest number that is not a perfect squarefor num in arr: if num not in perfect_squares: largest_not_square = num breakprint(largest_not_square) |
20
Time Complexity: O(nlogn)
Auxiliary Space: O(n) because we are storing the perfect squares in a list.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
