Dado un número natural N , la tarea es encontrar el número octal de N dígitos más grande que sea un cuadrado perfecto.
Ejemplos:
Entrada: N = 1
Salida: 4
Explicación:
4 es el número octal de 1 dígito más grande que también es un cuadrado perfecto
Entrada: N = 2
Salida: 61
Explicación:
49 es el número más grande que es un número octal de 2 dígitos y también un número perfecto cuadrado.
Por lo tanto 49 en Octal = 61
Planteamiento:
Se puede observar que la serie de números más grandes que también es un cuadrado perfecto en Octal es:
4, 61, 744, 7601, 77771, 776001…..
Como sabemos, los dígitos en el sistema octal aumentan cuando un número es mayor que 8 k , donde k denota el número de dígitos del número. Entonces, para cualquier número de N dígitos en el sistema numérico octal debe ser menor que el valor de 8 N+1 . Entonces, el término general que se puede derivar usando esta observación es:
Número octal de N dígitos = octal(pow(ceil(sqrt(pow(8, N))) -1, 2))
A continuación se muestra la implementación del enfoque anterior:
CPP
// C++ implementation to find the maximum
// N-digit octal number which is perfect square
#include <bits/stdc++.h>
using namespace std;
// Function to convert decimal number
// to a octal number
void decToOctal(int n)
{
// Array to store octal number
int octalNum[100];
// Counter for octal number array
int i = 0;
while (n != 0) {
// Store remainder in
// octal array
octalNum[i] = n % 8;
n = n / 8;
i++;
}
// Print octal number array
// in reverse order
for (int j = i - 1; j >= 0; j--)
cout << octalNum[j];
cout << "\n";
}
void nDigitPerfectSquares(int n)
{
// Largest n-digit perfect square
int decimal = pow(
ceil(sqrt(pow(8, n))) - 1, 2
);
decToOctal(decimal);
}
// Driver Code
int main()
{
int n = 2;
nDigitPerfectSquares(n);
return 0;
}
Java
// Java implementation to find the maximum
// N-digit octal number which is perfect square
import java.util.*;
import java.lang.*;
import java.io.*;
class GFG
{
// Function to convert decimal number
// to a octal number
static void decToOctal(int n)
{
// Array to store octal number
int octalNum[] = new int[100];
// Counter for octal number array
int i = 0;
while (n != 0)
{
// Store remainder in
// octal array
octalNum[i] = n % 8;
n = n / 8;
i++;
}
// Print octal number array
// in reverse order
for (int j = i - 1; j >= 0; j--)
System.out.print(octalNum[j]);
System.out.println("\n");
}
static void nDigitPerfectSquares(int n)
{
// Largest n-digit perfect square
int decimal = (int) Math.pow(Math.ceil(Math.sqrt(Math.pow(8, n))) - 1, 2);
decToOctal(decimal);
}
// Driver code
public static void main (String[] args)
{
int n = 2;
nDigitPerfectSquares(n);
}
}
// This code is contributed by nidhiva
Python3
# Python3 implementation to find the maximum # N-digit octal number which is perfect square from math import sqrt,ceil # Function to convert decimal number # to a octal number def decToOctal(n) : # Array to store octal number octalNum = [0]*100; # Counter for octal number array i = 0; while (n != 0) : # Store remainder in # octal array octalNum[i] = n % 8; n = n // 8; i += 1; # Print octal number array # in reverse order for j in range(i - 1, -1, -1) : print(octalNum[j], end= ""); print(); def nDigitPerfectSquares(n) : # Largest n-digit perfect square decimal = pow(ceil(sqrt(pow(8, n))) - 1, 2); decToOctal(decimal); # Driver Code if __name__ == "__main__" : n = 2; nDigitPerfectSquares(n); # This code is contributed by AnkitRai01
C#
// C# implementation to find the maximum
// N-digit octal number which is perfect square
using System;
class GFG
{
// Function to convert decimal number
// to a octal number
static void decToOctal(int n)
{
// Array to store octal number
int []octalNum = new int[100];
// Counter for octal number array
int i = 0;
while (n != 0)
{
// Store remainder in
// octal array
octalNum[i] = n % 8;
n = n / 8;
i++;
}
// Print octal number array
// in reverse order
for (int j = i - 1; j >= 0; j--)
Console.Write(octalNum[j]);
Console.WriteLine();
}
static void nDigitPerfectSquares(int n)
{
// Largest n-digit perfect square
int _decimal = (int) Math.Pow(Math.Ceiling(Math.Sqrt(Math.Pow(8, n))) - 1, 2);
decToOctal(_decimal);
}
// Driver code
public static void Main()
{
int n = 2;
nDigitPerfectSquares(n);
}
}
// This code is contributed by AnkitRai01
Javascript
<script>
// Javascript implementation to find the maximum
// N-digit octal number which is perfect square
// Function to convert decimal number
// to a octal number
function decToOctal(n)
{
// Array to store octal number
var octalNum = Array(100).fill(0);
// Counter for octal number array
var i = 0;
while (n != 0) {
// Store remainder in
// octal array
octalNum[i] = n % 8;
n = parseInt(n / 8);
i++;
}
// Print octal number array
// in reverse order
for (var j = i - 1; j >= 0; j--)
document.write(octalNum[j]);
document.write("<br>");
}
function nDigitPerfectSquares(n)
{
// Largest n-digit perfect square
var decimal = Math.pow(
Math.ceil(Math.sqrt(Math.pow(8, n))) - 1, 2
);
decToOctal(decimal);
}
// Driver Code
var n = 2;
nDigitPerfectSquares(n);
</script>
61
Complejidad de tiempo: O (log 8 n)
Espacio Auxiliar: O(1)