Número más pequeño cuyo cuadrado tiene N dígitos

Dado un número N , la tarea es encontrar el número más pequeño cuyo cuadrado tenga N dígitos.
Ejemplos: 
 

Entrada: N = 2 
Salida: 4 
Explicación: 
3 ² = 9, que tiene 1 dígito. 
4 ² = 16, que tiene 2 dígitos. 
Por lo tanto, 4 es el número más pequeño cuyo cuadrado tiene N dígitos.
Entrada: N = 3 
Salida: 10 
Explicación: 
10 ² = 100, que tiene 3 dígitos. 
 

Enfoque ingenuo: el enfoque más simple para resolver el problema es calcular el cuadrado de cada número a partir de y contar el número de dígitos en su cuadrado. Imprime el primer número cuyo cuadrado se obtiene que sea de N dígitos. 
Complejidad de Tiempo: O(√(10 ^N ))
Enfoque Eficiente: Para resolver el problema, necesitamos hacer las siguientes observaciones: 
 

El número más pequeño cuyo cuadrado tiene 1 dígito = 1 
El número más pequeño cuyo cuadrado tiene 2 dígitos = 4 
El número más pequeño cuyo cuadrado tiene 3 dígitos = 10 
El número más pequeño cuyo cuadrado tiene 4 dígitos = 32 
El número más pequeño cuyo cuadrado tiene 5 dígitos = 100
Por lo tanto, estos números forman una serie 1, 4, 10, 32, 100, 317, ……. 
 

Ahora, necesitamos encontrar una fórmula para el N ^-ésimo término de la serie. 
Los términos de la serie se pueden expresar de la siguiente forma: 
 

Si N = 1 , el número más pequeño posible es 1. 

Si N = 2 , el número más pequeño posible es 41. 

Si N = 3 , el número más pequeño posible es 10. 

 

Por lo tanto, podemos concluir que el N ^de la serie se puede expresar como 
 

Por lo tanto, para resolver el problema, solo necesitamos calcular ceil(10 ^{(N – 1)/ 2} ) para el entero N dado .
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ Program to find the smallest
// number whose square has N digits
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to return smallest number
// whose square has N digits
int smallestNum(int N)
{
 
    // Calculate N-th term of the series
    float x = pow(10.0, (N - 1) / 2.0);
    return ceil(x);
}
 
// Driver Code
int main()
{
    int N = 4;
    cout << smallestNum(N);
 
    return 0;
}

// Java program for above approach
class GFG{
 
// Function to return smallest number
// whose square has N digits
static int smallestNum(int N)
{
  
    // Calculate N-th term of the series
    float x = (float)(Math.pow(10, (N - 1) / 2.0));
    return (int)(Math.ceil(x));
}
 
// Driver code
public static void main(String[] args)
{
    int N = 4;
    System.out.print(smallestNum(N));
}
}
 
// This code is contributed by spp

# Python3 Program to find the smallest
# number whose square has N digits
import math;
 
# Function to return smallest number
# whose square has N digits
def smallestNum(N):
 
    # Calculate N-th term of the series
    x = pow(10.0, (N - 1) / 2.0);
    return math.ceil(x);
 
# Driver Code
N = 4;
print(smallestNum(N));
 
# This code is contributed by Code_mech

// C# program for above approach
using System;
class GFG{
 
// Function to return smallest number
// whose square has N digits
static int smallestNum(int N)
{
 
    // Calculate N-th term of the series
    float x = (float)(Math.Pow(10, (N - 1) / 2.0));
    return (int)(Math.Ceiling(x));
}
 
// Driver code
public static void Main()
{
    int N = 4;
    Console.Write(smallestNum(N));
}
}
 
// This code is contributed by Code_Mech

<script>
// java script  Program to find the smallest
// number whose square has N digits
// Function to return smallest number
// whose square has N digits
function smallestNum(N)
{
 
    // Calculate N-th term of the series
    x = Math.pow(10.0, (N - 1) / 2.0);
    return Math.ceil(x);
}
 
// Driver Code
let N = 4;
document.write(smallestNum(N));
     
// This code is contributed by Gottumukkala Bobby
</script>

32

Complejidad de tiempo: O(log(N))  
Espacio auxiliar: O(1)