Comprueba si un número dado N es un cuadrado perfecto o no. En caso afirmativo, devuelva el número del cual es un cuadrado perfecto, de lo contrario, imprima -1.
Ejemplos:
Entrada: N = 4900
Salida 70
Explicación:
4900 es un número cuadrado perfecto de 70 porque 70 * 70 = 4900Entrada: N = 81
Salida: 9
Explicación:
81 es un número cuadrado perfecto de 9 porque 9 * 9 = 81
Enfoque: Para resolver el problema mencionado anteriormente, utilizaremos el algoritmo de búsqueda binaria.
- Encuentre el elemento medio desde el inicio y el último valor y compare el valor del cuadrado de medio (medio * medio) con N.
- Si es igual, devuelva el valor medio; de lo contrario, verifique si el cuadrado (medio * medio) es mayor que N , luego llame recursivamente con el mismo valor inicial pero cambió al último valor medio-1 y si el cuadrado (medio * medio) es menor que la N luego llama recursiva con el mismo último valor pero cambió el valor de inicio.
- Si N no es una raíz cuadrada, devuelva -1.
A continuación se muestra la implementación del enfoque anterior:
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 number int 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 code int 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 Search import java.util.*; class GFG { // Function to check for // perfect square number static 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 code public 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 = 65 print (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 number function 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 code let N = 65; document.write(checkPerfectSquare(N, 1, N)); // This code is contributed by rishavmahato348 </script>
-1
Complejidad de tiempo: O (Iniciar sesión)
Publicación traducida automáticamente
Artículo escrito por Eternity_vaibhav y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA