Dado un entero positivo 
. La tarea es encontrar el número cuadrado perfecto más cercano a N y los pasos necesarios para llegar a este número desde N .
Nota: El cuadrado perfecto más cercano a N puede ser menor, igual o mayor que N y los pasos se conocen como la diferencia entre N y el cuadrado perfecto más cercano.
Ejemplos:
Entrada: N = 1500
Salida: Cuadrado perfecto = 1521, Pasos = 21
Para N = 1500
El cuadrado perfecto más cercano mayor que N es 1521.
Por lo tanto, los pasos requeridos son 21.
El cuadrado perfecto más cercano menor que N es 1444.
Por lo tanto, los pasos requeridos son 56.
El el mínimo de estos dos es 1521 con pasos 21.
Entrada: N = 2
Salida: Cuadrado perfecto = 1, Pasos = 1
Para N = 2
El cuadrado perfecto más cercano mayor que N es 4.
Por lo tanto, los pasos requeridos son 2.
El cuadrado perfecto más cercano menor que N es 1.
Entonces, los pasos requeridos son 1.
El mínimo de estos dos es 1.
Enfoque 1:
- Si N es un cuadrado perfecto , imprima N y los pasos como 0 .
- De lo contrario, encuentra el primer número cuadrado perfecto > N y observa su diferencia con N .
- Luego, encuentre el primer número cuadrado perfecto < N y observe su diferencia con N .
- E imprima el cuadrado perfecto que resulte en el mínimo de estas dos diferencias obtenidas y también la diferencia como los pasos mínimos.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to find the closest perfect square
// taking minimum steps to reach from a number
#include <bits/stdc++.h>
using namespace std;
// Function to check if a number is
// perfect square or not
bool isPerfect(int N)
{
if ((sqrt(N) - floor(sqrt(N))) != 0)
return false;
return true;
}
// Function to find the closest perfect square
// taking minimum steps to reach from a number
void getClosestPerfectSquare(int N)
{
if (isPerfect(N)) {
cout << N << " "
<< "0" << endl;
return;
}
// Variables to store first perfect
// square number
// above and below N
int aboveN = -1, belowN = -1;
int n1;
// Finding first perfect square
// number greater than N
n1 = N + 1;
while (true) {
if (isPerfect(n1)) {
aboveN = n1;
break;
}
else
n1++;
}
// Finding first perfect square
// number less than N
n1 = N - 1;
while (true) {
if (isPerfect(n1)) {
belowN = n1;
break;
}
else
n1--;
}
// Variables to store the differences
int diff1 = aboveN - N;
int diff2 = N - belowN;
if (diff1 > diff2)
cout << belowN << " " << diff2;
else
cout << aboveN << " " << diff1;
}
// Driver code
int main()
{
int N = 1500;
getClosestPerfectSquare(N);
}
// This code is contributed by
// Surendra_Gangwar
Java
// Java program to find the closest perfect square
// taking minimum steps to reach from a number
class GFG {
// Function to check if a number is
// perfect square or not
static boolean isPerfect(int N)
{
if ((Math.sqrt(N) - Math.floor(Math.sqrt(N))) != 0)
return false;
return true;
}
// Function to find the closest perfect square
// taking minimum steps to reach from a number
static void getClosestPerfectSquare(int N)
{
if (isPerfect(N)) {
System.out.println(N + " "
+ "0");
return;
}
// Variables to store first perfect
// square number
// above and below N
int aboveN = -1, belowN = -1;
int n1;
// Finding first perfect square
// number greater than N
n1 = N + 1;
while (true) {
if (isPerfect(n1)) {
aboveN = n1;
break;
}
else
n1++;
}
// Finding first perfect square
// number less than N
n1 = N - 1;
while (true) {
if (isPerfect(n1)) {
belowN = n1;
break;
}
else
n1--;
}
// Variables to store the differences
int diff1 = aboveN - N;
int diff2 = N - belowN;
if (diff1 > diff2)
System.out.println(belowN + " " + diff2);
else
System.out.println(aboveN + " " + diff1);
}
// Driver code
public static void main(String args[])
{
int N = 1500;
getClosestPerfectSquare(N);
}
}
Python3
# Python3 program to find the closest # perfect square taking minimum steps # to reach from a number # Function to check if a number is # perfect square or not from math import sqrt, floor def isPerfect(N): if (sqrt(N) - floor(sqrt(N)) != 0): return False return True # Function to find the closest perfect square # taking minimum steps to reach from a number def getClosestPerfectSquare(N): if (isPerfect(N)): print(N, "0") return # Variables to store first perfect # square number above and below N aboveN = -1 belowN = -1 n1 = 0 # Finding first perfect square # number greater than N n1 = N + 1 while (True): if (isPerfect(n1)): aboveN = n1 break else: n1 += 1 # Finding first perfect square # number less than N n1 = N - 1 while (True): if (isPerfect(n1)): belowN = n1 break else: n1 -= 1 # Variables to store the differences diff1 = aboveN - N diff2 = N - belowN if (diff1 > diff2): print(belowN, diff2) else: print(aboveN, diff1) # Driver code N = 1500 getClosestPerfectSquare(N) # This code is contributed # by sahishelangia
C#
// C# program to find the closest perfect square
// taking minimum steps to reach from a number
using System;
class GFG {
// Function to check if a number is
// perfect square or not
static bool isPerfect(int N)
{
if ((Math.Sqrt(N) - Math.Floor(Math.Sqrt(N))) != 0)
return false;
return true;
}
// Function to find the closest perfect square
// taking minimum steps to reach from a number
static void getClosestPerfectSquare(int N)
{
if (isPerfect(N)) {
Console.WriteLine(N + " "
+ "0");
return;
}
// Variables to store first perfect
// square number
// above and below N
int aboveN = -1, belowN = -1;
int n1;
// Finding first perfect square
// number greater than N
n1 = N + 1;
while (true) {
if (isPerfect(n1)) {
aboveN = n1;
break;
}
else
n1++;
}
// Finding first perfect square
// number less than N
n1 = N - 1;
while (true) {
if (isPerfect(n1)) {
belowN = n1;
break;
}
else
n1--;
}
// Variables to store the differences
int diff1 = aboveN - N;
int diff2 = N - belowN;
if (diff1 > diff2)
Console.WriteLine(belowN + " " + diff2);
else
Console.WriteLine(aboveN + " " + diff1);
}
// Driver code
public static void Main()
{
int N = 1500;
getClosestPerfectSquare(N);
}
}
// This code is contributed by anuj_67..
PHP
<?php
// PHP program to find the closest perfect
// square taking minimum steps to reach
// from a number
// Function to check if a number is
// perfect square or not
function isPerfect($N)
{
if ((sqrt($N) - floor(sqrt($N))) != 0)
return false;
return true;
}
// Function to find the closest perfect square
// taking minimum steps to reach from a number
function getClosestPerfectSquare($N)
{
if (isPerfect($N))
{
echo $N, " ", "0", "\n";
return;
}
// Variables to store first perfect
// square number
// above and below N
$aboveN = -1;
$belowN = -1;
$n1;
// Finding first perfect square
// number greater than N
$n1 = $N + 1;
while (true)
{
if (isPerfect($n1))
{
$aboveN = $n1;
break;
}
else
$n1++;
}
// Finding first perfect square
// number less than N
$n1 = $N - 1;
while (true)
{
if (isPerfect($n1))
{
$belowN = $n1;
break;
}
else
$n1--;
}
// Variables to store the differences
$diff1 = $aboveN - $N;
$diff2 = $N - $belowN;
if ($diff1 > $diff2)
echo $belowN, " " , $diff2;
else
echo $aboveN, " ", $diff1;
}
// Driver code
$N = 1500;
getClosestPerfectSquare($N);
// This code is contributed by ajit.
?>
Javascript
<script>
// Javascript program to find
// the closest perfect square
// taking minimum steps to reach
// from a number
// Function to check if a number is
// perfect square or not
function isPerfect(N)
{
if ((Math.sqrt(N) -
Math.floor(Math.sqrt(N))) != 0)
return false;
return true;
}
// Function to find the closest perfect square
// taking minimum steps to reach from a number
function getClosestPerfectSquare(N)
{
if (isPerfect(N)) {
document.write(N + " " + "0" + "</br>");
return;
}
// Variables to store first perfect
// square number
// above and below N
let aboveN = -1, belowN = -1;
let n1;
// Finding first perfect square
// number greater than N
n1 = N + 1;
while (true) {
if (isPerfect(n1)) {
aboveN = n1;
break;
}
else
n1++;
}
// Finding first perfect square
// number less than N
n1 = N - 1;
while (true) {
if (isPerfect(n1)) {
belowN = n1;
break;
}
else
n1--;
}
// Variables to store the differences
let diff1 = aboveN - N;
let diff2 = N - belowN;
if (diff1 > diff2)
document.write(belowN + " " + diff2);
else
document.write(aboveN + " " + diff1);
}
let N = 1500;
getClosestPerfectSquare(N);
</script>
Producción
1521 21
Complejidad de tiempo: O(n), donde n es el número dado ya que estamos usando la fuerza bruta para encontrar los cuadrados perfectos arriba y abajo.
Complejidad espacial: O(1), ya que no se ha tomado espacio extra.
Enfoque 2:
El método anterior puede llevar mucho tiempo para números más grandes, es decir, superiores a 10 6 . Desearíamos tener una forma más rápida de hacerlo.
- Aquí, usaremos las matemáticas para resolver el problema anterior en una complejidad de tiempo constante.
- Primero encontraremos la raíz cuadrada del número n.
- Comprobaremos si n era un cuadrado perfecto, y si lo fuera, devolveremos 0 allí mismo.
- De lo contrario, usaremos su raíz cuadrada para encontrar los números cuadrados perfectos justo arriba y abajo, y devolveremos el que está a la distancia mínima.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to find the closest perfect square
// taking minimum steps to reach from a number
#include <bits/stdc++.h>
using namespace std;
// Function to find the closest perfect square
// taking minimum steps to reach from a number
void getClosestPerfectSquare(int N)
{
int x = sqrt(N);
//Checking if N is a perfect square
if((x*x)==N){
cout<<N<<" "<<0;
return;
}
// If N is not a perfect square,
// squaring x and x+1 gives us the
// just below and above perfect squares
// Variables to store perfect
// square number just
// above and below N
int aboveN = (x+1)*(x+1), belowN = x*x;
// Variables to store the differences
int diff1 = aboveN - N;
int diff2 = N - belowN;
if (diff1 > diff2)
cout << belowN << " " << diff2;
else
cout << aboveN << " " << diff1;
}
// Driver code
int main()
{
int N = 1500;
getClosestPerfectSquare(N);
}
// This code is contributed by
// Rohit Kumar
Java
// Java program for the above approach
public class GFG {
// Function to find the closest perfect square
// taking minimum steps to reach from a number
static void getClosestPerfectSquare(int N)
{
int x = (int)Math.sqrt(N);
//Checking if N is a perfect square
if((x*x)==N){
System.out.println(N);
return;
}
// If N is not a perfect square,
// squaring x and x+1 gives us the
// just below and above perfect squares
// Variables to store perfect
// square number just
// above and below N
int aboveN = (x+1)*(x+1), belowN = x*x;
// Variables to store the differences
int diff1 = aboveN - N;
int diff2 = N - belowN;
if (diff1 > diff2)
System.out.println(belowN+" "+diff2);
else
System.out.println(aboveN+" "+diff1);
}
// Driver Code
public static void main (String[] args)
{
int N = 1500;
getClosestPerfectSquare(N);
}
}
// This code is contributed by aditya942003patil
Python3
# Python3 program to find the closest # perfect square taking minimum steps # to reach from a number from math import sqrt, floor # Function to find the closest perfect square # taking minimum steps to reach from a number def getClosestPerfectSquare(N): x = floor(sqrt(N)) # Checking if N is itself a perfect square if (sqrt(N) - floor(sqrt(N)) == 0): print(N,0) return # Variables to store first perfect # square number above and below N aboveN = (x+1)*(x+1) belowN = x*x # Variables to store the differences diff1 = aboveN - N diff2 = N - belowN if (diff1 > diff2): print(belowN, diff2) else: print(aboveN, diff1) # Driver code N = 1500 getClosestPerfectSquare(N) # This code is contributed # by Rohit Kumar
Producción
1521 21
Complejidad de tiempo: O(1), ya que aquí solo hemos usado matemáticas.
Complejidad espacial: O(1), ya que no se ha tomado espacio extra.
Publicación traducida automáticamente
Artículo escrito por rachana soma y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA