N-ésimo número no cuadrado

Dado n , encuentre el n-ésimo número que no es un cuadrado perfecto entre los números naturales (1, 2, 3, 4, 5, 6, …)

Ejemplos: 

Input : 3
Output : 5
First three non-square numbers are 2, 3
and 5

Input : 5
Output : 7

Input : 16
Output : 20

Mirando la declaración del problema, podemos llegar a un enfoque directo de fuerza bruta. Podemos partir de n = 1 y empezar a comprobar si cada uno de ellos es un cuadrado perfecto o no. Entonces podemos llegar al enésimo número no cuadrado. 
Sin embargo, el enfoque anterior es muy lento ya que busca cada uno en cada número más pequeño que el objetivo cada vez. 
Podemos observar que la serie considerada es 2, 3, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15, 17,…. 
Podemos llegar a la fórmula de tiempo constante para el número n en esta secuencia, por inspección. 
.
La corrección de la fórmula puede probarse por el Principio de Inducción Matemática.

A continuación se muestra la implementación de la fórmula anterior. 

// CPP program to find n-th non-square number.
#include <bits/stdc++.h>
 
using namespace std;
 
// function to find the nth Non-Square Number
int findNthNonSquare(int n)
{
    // conversion from int to long double is
    // necessary in order to preserve decimal
    // places after square root.
    long double x = (long double)n;
 
    // calculating the result
    long double ans = x + floor(0.5 + sqrt(x));
 
    return (int)ans;
}
 
// Driver code
int main()
{
    // initializing the term number
    int n = 16;
 
    // Print the result
    cout << "The " << n << "th Non-Square number is ";
    cout << findNthNonSquare(n);
 
    return 0;
}

// Java program to find
// n-th non-square number.
import java.io.*;
import java.util.*;
import java.lang.*;
 
class GFG
{
     
// function to find the
// nth Non-Square Number
static int findNthNonSquare(int n)
{
    // conversion from int to
    // long double is necessary
    // in order to preserve decimal
    // places after square root.
    double x = (double)n;
 
    // calculating the result
    double ans = x + Math.floor(0.5 +
                     Math.sqrt(x));
 
    return (int)ans;
}
 
// Driver code
public static void main(String[] args)
{
    // initializing
    // the term number
    int n = 16;
 
    // Print the result
    System.out.print("The " + n +
                     "th Non-Square number is ");
    System.out.print(findNthNonSquare(n));
}
}

# Python3 program to find n-th
# non-square number.
import math
 
# function to find the nth
# Non-Square Number
def findNthNonSquare(n):
 
    # conversion from int to long
    # double is necessary in order
    # to preserve decimal places
    # after square root.
    x = n;
 
    # calculating the result
    ans = x + math.floor(0.5 + math.sqrt(x));
 
    return int(ans);
 
# Driver code
 
# initializing the term number
n = 16;
 
# Print the result
print("The", n, "th Non-Square number is",
                     findNthNonSquare(n));
 
# This code is contributed by mits

// C# program to find
// n-th non-square number.
using System;
 
class GFG
{
     
// function to find the
// nth Non-Square Number
static int findNthNonSquare(int n)
{
    // conversion from int
    // to long double is
    // necessary in order
    // to preserve decimal
    // places after square
    // root.
    double x = (double)n;
 
    // calculating the result
    double ans = x + Math.Floor(0.5 +
                     Math.Sqrt(x));
 
    return (int)ans;
}
 
// Driver code
public static void Main()
{
    // initializing
    // the term number
    int n = 16;
 
    // Print the result
    Console.Write("The " + n +
                  "th Non-Square " +
                      "number is ");
    Console.Write(findNthNonSquare(n));
}
}
 
// This code is contributed
// by anuj_67.

<?php
// PHP program to find n-th
// non-square number.
 
// function to find the nth
// Non-Square Number
function findNthNonSquare($n)
{
    // conversion from int to long
    // double is necessary in order
    // to preserve decimal places
    // after square root.
    $x = $n;
 
    // calculating the result
    $ans = $x + floor(0.5 + sqrt($x));
 
    return (int)$ans;
}
 
// Driver code
 
// initializing the term number
$n = 16;
 
// Print the result
echo "The " . $n .
     "th Non-Square number is ";
echo findNthNonSquare($n);
 
// This Code is Contributed by mits
?>

<script>
 
// Javascript program to find
// n-th non-square number.
 
// Function to find the
// nth Non-Square Number
function findNthNonSquare(n)
{
     
    // Conversion from var to
    // var var is necessary
    // in order to preserve decimal
    // places after square root.
    var x =  n;
 
    // Calculating the result
    var ans = x + Math.floor(0.5 + Math.sqrt(x));
 
    return parseInt(ans);
}
 
// Driver code
 
// Initializing
// the term number
var n = 16;
 
// Print the result
document.write("The " + n + "th Non-Square number is ");
document.write(findNthNonSquare(n));
 
// This code is contributed by todaysgaurav
 
</script>

Producción: 

The 16th Non-Square number is 20

Complejidad del tiempo  . 
Complejidad espacial