El cuadrado perfecto más cercano y su distancia

Dado un entero positivo  N        . 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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *