Check if a given number N is a perfect square or not. If yes then return the number of which it is a perfect square, Else print -1.
Examples:
Input: N = 4900
Output 70
Explanation:
4900 is a perfect square number of 70 because 70 * 70 = 4900Input: N = 81
Output: 9
Explanation:
81 is a perfect square number of 9 because 9 * 9 = 81
Approach: To solve the problem mentioned above we will use the Binary Search Algorithm.
- Find the mid element from the start and last value and compare the value of the square of mid(mid*mid) with N.
- If it is equal then return the mid otherwise check if the square(mid*mid) is greater than N then recursive call with the same start value but changed last to mid-1 value and if the square(mid*mid) is less than the N then recursive call with the same last value but changed start value.
- If the N is not a square root then return -1.
Below is the implementation of above approach:
C++
// C++ program to check if a// given number is Perfect// square using Binary Search#include <iostream>using namespace std;// function to check for// perfect square numberint checkPerfectSquare( long int N, long int start, long int last){ // Find the mid value // from start and last long int mid = (start + last) / 2; if (start > last) { return -1; } // check if we got the number which // is square root of the perfect // square number N if (mid * mid == N) { return mid; } // if the square(mid) is greater than N // it means only lower values then mid // will be possibly the square root of N else if (mid * mid > N) { return checkPerfectSquare( N, start, mid - 1); } // if the square(mid) is less than N // it means only higher values then mid // will be possibly the square root of N else { return checkPerfectSquare( N, mid + 1, last); }}// Driver codeint main(){ long int N = 65; cout << checkPerfectSquare(N, 1, N); return 0;} |
Java
// Java program to check if a// given number is Perfect// square using Binary Searchimport java.util.*;class GFG {// Function to check for// perfect square numberstatic int checkPerfectSquare(long N, long start, long last){ // Find the mid value // from start and last long mid = (start + last) / 2; if (start > last) { return -1; } // Check if we got the number which // is square root of the perfect // square number N if (mid * mid == N) { return (int)mid; } // If the square(mid) is greater than N // it means only lower values then mid // will be possibly the square root of N else if (mid * mid > N) { return checkPerfectSquare(N, start, mid - 1); } // If the square(mid) is less than N // it means only higher values then mid // will be possibly the square root of N else { return checkPerfectSquare(N, mid + 1, last); }}// Driver codepublic static void main(String[] args){ long N = 65; System.out.println(checkPerfectSquare(N, 1, N));}}// This code is contributed by offbeat |
Python3
# Python3 program to check if a # given number is perfect # square using Binary Search # Function to check for # perfect square number def checkPerfectSquare(N, start, last): # Find the mid value # from start and last mid = int((start + last) / 2) if (start > last): return -1 # Check if we got the number which # is square root of the perfect # square number N if (mid * mid == N): return mid # If the square(mid) is greater than N # it means only lower values then mid # will be possibly the square root of N elif (mid * mid > N): return checkPerfectSquare(N, start, mid - 1) # If the square(mid) is less than N # it means only higher values then mid # will be possibly the square root of N else: return checkPerfectSquare(N, mid + 1, last)# Driver code N = 65print (checkPerfectSquare(N, 1, N)) # This code is contributed by PratikBasu |
C#
// C# program to check if a // given number is Perfect // square using Binary Search using System;class GFG{// Function to check for // perfect square number public static int checkPerfectSquare(int N, int start, int last){ // Find the mid value // from start and last int mid = (start + last) / 2; if (start > last) { return -1; } // Check if we got the number which // is square root of the perfect // square number N if (mid * mid == N) { return mid; } // If the square(mid) is greater than N // it means only lower values then mid // will be possibly the square root of N else if (mid * mid > N) { return checkPerfectSquare(N, start, mid - 1); } // If the square(mid) is less than N // it means only higher values then mid // will be possibly the square root of N else { return checkPerfectSquare(N, mid + 1, last); }}// Driver code public static int Main(){ int N = 65; Console.Write(checkPerfectSquare(N, 1, N)); return 0;}}// This code is contributed by sayesha |
Javascript
<script>// Javascript program to check if a// given number is Perfect// square using Binary Search// Function to check for// perfect square numberfunction checkPerfectSquare(N, start, last){ // Find the mid value // from start and last let mid = parseInt((start + last) / 2); if (start > last) { return -1; } // Check if we got the number which // is square root of the perfect // square number N if (mid * mid == N) { return mid; } // If the square(mid) is greater than N // it means only lower values then mid // will be possibly the square root of N else if (mid * mid > N) { return checkPerfectSquare( N, start, mid - 1); } // If the square(mid) is less than N // it means only higher values then mid // will be possibly the square root of N else { return checkPerfectSquare( N, mid + 1, last); }}// Driver codelet N = 65;document.write(checkPerfectSquare(N, 1, N));// This code is contributed by rishavmahato348</script> |
Output:
-1
Time Complexity: O(Logn)
Auxiliary Space: O(Logn) for recursive stack space.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
[…] all subarrays using the Prefix Sum Array. For each subarray, check if the sum of the subarray is a perfect square or not. If found to be true for any subarray, then print the start and end indices of that […]