Dado un número entero N, encuentre el número de N dígitos más pequeño tal que la suma del cuadrado de los dígitos (en representación decimal) del número también sea un cuadrado perfecto. Si no existe tal número, imprima -1.
Ejemplos:
Entrada: N = 2
Salida: 34
Explicación:
El número de 2 dígitos más pequeño posible cuya suma del cuadrado de los dígitos es un cuadrado perfecto es 34 porque 3 2 + 4 2 = 5 2 .
Entrada: N = 1
Salida: 1
Explicación:
El número de 1 dígito más pequeño posible es 1 mismo.
Método 1:
Para resolver el problema mencionado anteriormente podemos usar Backtracking . Dado que queremos encontrar el número mínimo de N dígitos que satisfaga la condición dada, la respuesta tendrá dígitos en orden no decreciente. Por lo tanto, generamos los números posibles recursivamente haciendo un seguimiento de lo siguiente en cada paso recursivo:
- posición: la posición actual del paso recursivo, es decir, qué dígito de posición se está colocando.
- prev: el dígito anterior colocado porque el dígito actual tiene que ser mayor que igual al anterior.
- suma: la suma de los cuadrados de los dígitos colocados hasta ahora. Cuando se colocan dígitos, esto se usará para verificar si la suma de los cuadrados de todos los dígitos colocados es un cuadrado perfecto o no.
- Un vector que almacena todos los dígitos que se han colocado hasta esta posición.
Si colocar un dígito en una posición y pasar al siguiente paso recursivo conduce a una posible solución, devuelva 1, de lo contrario retroceda.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find Smallest N
// digit number whose sum of square
// of digits is a Perfect Square
#include <bits/stdc++.h>
using namespace std;
// function to check if
// number is a perfect square
int isSquare(int n)
{
int k = sqrt(n);
return (k * k == n);
}
// function to calculate the
// smallest N digit number
int calculate(int pos, int prev,
int sum, vector<int>& v)
{
if (pos == v.size())
return isSquare(sum);
// place digits greater than equal to prev
for (int i = prev; i <= 9; i++) {
v[pos] = i;
sum += i * i;
// check if placing this digit leads
// to a solution then return it
if (calculate(pos + 1, i, sum, v))
return 1;
// else backtrack
sum -= i * i;
}
return 0;
}
string minValue(int n)
{
vector<int> v(n);
if (calculate(0, 1, 0, v)) {
// create a string representing
// the N digit number
string answer = "";
for (int i = 0; i < v.size(); i++)
answer += char(v[i] + '0');
return answer;
}
else
return "-1";
}
// driver code
int main()
{
// initialise N
int N = 2;
cout << minValue(N);
return 0;
}
Java
// Java implementation to find Smallest N
// digit number whose sum of square
// of digits is a Perfect Square
class GFG{
// function to check if
// number is a perfect square
static int isSquare(int n)
{
int k = (int)Math.sqrt(n);
return k * k == n ? 1 : 0;
}
// Function to calculate the
// smallest N digit number
static int calculate(int pos, int prev,
int sum, int[] v)
{
if (pos == v.length)
return isSquare(sum);
// Place digits greater than equal to prev
for(int i = prev; i <= 9; i++)
{
v[pos] = i;
sum += i * i;
// Check if placing this digit leads
// to a solution then return it
if (calculate(pos + 1, i, sum, v) != 0)
return 1;
// Else backtrack
sum -= i * i;
}
return 0;
}
static String minValue(int n)
{
int[] v = new int[n];
if (calculate(0, 1, 0, v) != 0)
{
// Create a string representing
// the N digit number
String answer = "";
for(int i = 0; i < v.length; i++)
answer += (char)(v[i] + '0');
return answer;
}
else
return "-1";
}
// Driver code
public static void main(String[] args)
{
// Initialise N
int N = 2;
System.out.println(minValue(N));
}
}
// This code is contributed by jrishabh99
Python3
# Python3 implementation to find Smallest N
# digit number whose sum of square
# of digits is a Perfect Square
from math import sqrt
# function to check if
# number is a perfect square
def isSquare(n):
k = int(sqrt(n))
return (k * k == n)
# function to calculate the
# smallest N digit number
def calculate(pos, prev, sum, v):
if (pos == len(v)):
return isSquare(sum)
# place digits greater than equal to prev
for i in range(prev, 9 + 1):
v[pos] = i
sum += i * i
# check if placing this digit leads
# to a solution then return it
if (calculate(pos + 1, i, sum, v)):
return 1
# else backtrack
sum -= i * i
return 0
def minValue(n):
v = [0]*(n)
if (calculate(0, 1, 0, v)):
# create a representing
# the N digit number
answer = ""
for i in range(len(v)):
answer += chr(v[i] + ord('0'))
return answer
else:
return "-1"
# Driver code
if __name__ == '__main__':
# initialise N
N = 2
print(minValue(N))
# This code is contributed by mohit kumar 29
C#
// C# implementation to find Smallest N
// digit number whose sum of square
// of digits is a Perfect Square
using System;
class GFG{
// function to check if
// number is a perfect square
static int isSquare(int n)
{
int k = (int)Math.Sqrt(n);
return k * k == n ? 1 : 0;
}
// Function to calculate the
// smallest N digit number
static int calculate(int pos, int prev,
int sum, int[] v)
{
if (pos == v.Length)
return isSquare(sum);
// Place digits greater than equal to prev
for(int i = prev; i <= 9; i++)
{
v[pos] = i;
sum += i * i;
// Check if placing this digit leads
// to a solution then return it
if (calculate(pos + 1, i, sum, v) != 0)
return 1;
// Else backtrack
sum -= i * i;
}
return 0;
}
static string minValue(int n)
{
int[] v = new int[n];
if (calculate(0, 1, 0, v) != 0)
{
// Create a string representing
// the N digit number
string answer = "";
for(int i = 0; i < v.Length; i++)
answer += (char)(v[i] + '0');
return answer;
}
else
return "-1";
}
// Driver code
public static void Main()
{
// Initialise N
int N = 2;
Console.Write(minValue(N));
}
}
Javascript
<script>
// Javascript implementation to find Smallest N
// digit number whose sum of square
// of digits is a Perfect Square
// function to check if
// number is a perfect square
function isSquare(n)
{
let k = Math.floor(Math.sqrt(n));
return k * k == n ? 1 : 0;
}
// Function to calculate the
// smallest N digit number
function calculate(pos, prev, sum, v)
{
if (pos == v.length)
return isSquare(sum);
// Place digits greater than equal to prev
for(let i = prev; i <= 9; i++)
{
v[pos] = i;
sum += i * i;
// Check if placing this digit leads
// to a solution then return it
if (calculate(pos + 1, i, sum, v) != 0)
return 1;
// Else backtrack
sum -= (i * i);
}
return 0;
}
function minValue(n)
{
let v = Array.from({length: n}, (_, i) => 0);
if (calculate(0, 1, 0, v) != 0)
{
// Create a string representing
// the N digit number
let answer = "";
for(let i = 0; i < v.length; i++)
answer += (v[i] + 0);
return answer;
}
else
return "-1";
}
// Driver Code
// Initialise N
let N = 2;
document.write(minValue(N));
// This code is contributed by sanjoy_62.
</script>
Producción
34
Complejidad de tiempo: O(sqrt(n))
Espacio Auxiliar: O(n)
Método 2:
el problema mencionado anteriormente también se puede resolver utilizando la programación dinámica . Si observamos la pregunta detenidamente, vemos que se puede convertir en el problema estándar de cambio de moneda . Dado N como el número de dígitos, la respuesta base será N 1, la suma del cuadrado de cuyos dígitos será N.
- Si N en sí mismo es un cuadrado perfecto, entonces N por 1 será la respuesta final.
- De lo contrario, tendremos que reemplazar algunos 1 en la respuesta con otros dígitos del 2 al 9. Cada reemplazo en el dígito aumentará la suma del cuadrado en una cierta cantidad y dado que 1 se puede cambiar a solo otros 8 dígitos posibles, solo hay 8 incrementos posibles. Por ejemplo, si 1 se cambia a 2, entonces el incremento será 2 2 – 1 2 = 3. De manera similar, todos los cambios posibles son: {3, 8, 15, 24, 35, 48, 63, 80}.
Entonces, el problema ahora se puede interpretar como si tuviera 8 tipos de monedas de los valores antes mencionados y podemos usar cualquier moneda cualquier número de veces para crear la suma requerida. La suma de cuadrados estará en el rango de N (todos los dígitos son 1) a 81 * N (todos los dígitos son 9). Solo tenemos que considerar sumas cuadradas perfectas en el rango y usar la idea del cambio de moneda para encontrar los N dígitos que estarán en la respuesta. Un punto importante que debemos tener en cuenta es que tenemos que encontrar el número de N dígitos más pequeño, no el número con la suma cuadrada de dígitos más pequeña.
A continuación se muestra la implementación del enfoque mencionado anteriormente:
C++
// C++ implementation to find the Smallest
// N digit number whose sum of square
// of digits is a Perfect Square
#include <bits/stdc++.h>
using namespace std;
long long value[8100006];
int first[8100006];
// array for all possible changes
int coins[8] = { 3, 8, 15, 24, 35, 48, 63, 80 };
void coinChange()
{
const long long inf = INT_MAX;
// iterating till 81 * N
// since N is at max 10^5
for (int x = 1; x <= 8100005; x++) {
value[x] = inf;
for (auto c : coins) {
if (x - c >= 0 && value[x - c] + 1 < value[x]) {
value[x] = min(value[x], value[x - c] + 1);
// least value of coin
first[x] = c;
}
}
}
}
// function to find the
// minimum possible value
string minValue(int n)
{
// applying coin change for all the numbers
coinChange();
string answer = "";
// check if number is
// perfect square or not
if ((sqrt(n) * sqrt(n)) == n) {
for (int i = 0; i < n; i++)
answer += "1";
return answer;
}
long long hi = 81 * n;
long long lo = sqrt(n);
// keeps a check whether
// number is found or not
bool found = false;
long long upper = 81 * n;
long long lower = n;
// sorting suffix strings
string suffix;
bool suf_init = false;
while ((lo * lo) <= hi) {
lo++;
long long curr = lo * lo;
long long change = curr - n;
if (value[change] <= lower) {
// build a suffix string
found = true;
if (lower > value[change]) {
// number to be used for updation of lower,
// first values that will be used
// to construct the final number later
lower = value[change];
upper = change;
suffix = "";
suf_init = true;
int len = change;
while (len > 0) {
int k = sqrt(first[len] + 1);
suffix = suffix + char(k + 48);
len = len - first[len];
}
}
else if (lower == value[change]) {
string tempsuf = "";
int len = change;
while (len > 0) {
int k = sqrt(first[len] + 1);
tempsuf = tempsuf + char(k + 48);
len = len - first[len];
}
if (tempsuf < suffix or suf_init == false) {
lower = value[change];
upper = change;
suffix = tempsuf;
suf_init = true;
}
}
}
}
// check if number is found
if (found) {
// construct the number from first values
long long x = lower;
for (int i = 0; i < (n - x); i++)
answer += "1";
long long temp = upper;
// fill in rest of the digits
while (temp > 0) {
int dig = sqrt(first[temp] + 1);
temp = temp - first[temp];
answer += char(dig + '0');
}
return answer;
}
else
return "-1";
}
// driver code
int main()
{
// initialise N
int N = 2;
cout << minValue(N);
return 0;
}
Java
// Java implementation to find the Smallest
// N digit number whose sum of square
// of digits is a Perfect Square
import java.util.*;
class GFG {
static long[] value = new long[(int)8100006];
static int[] first = new int[8100006];
// array for all possible changes
static int coins[] = { 3, 8, 15, 24, 35, 48, 63, 80 };
public static void coinChange()
{
final long inf = Integer.MAX_VALUE;
// iterating till 81 * N
// since N is at max 10^5
for (int x = 1; x <= 8100005; x++) {
value[x] = inf;
for (int c : coins) {
if (x - c >= 0
&& value[x - c] + 1 < value[x]) {
value[x] = Math.min(value[x],
value[x - c] + 1);
// least value of coin
first[x] = c;
}
}
}
}
// function to find the
// minimum possible value
public static String minValue(int n)
{
// applying coin change for all the numbers
coinChange();
String answer = "";
// check if number is
// perfect square or not
if ((Math.sqrt(n) * Math.sqrt(n)) == n) {
for (int i = 0; i < n; i++)
answer += "1";
return answer;
}
long hi = 81 * n;
long lo = (long)Math.sqrt(n);
// keeps a check whether
// number is found or not
boolean found = false;
long upper = 81 * n;
long lower = n;
// sorting suffix strings
String suffix = "";
boolean suf_init = false;
while ((lo * lo) <= hi) {
lo++;
long curr = lo * lo;
long change = curr - n;
if (value[(int)change] <= lower) {
// build a suffix string
found = true;
if (lower > value[(int)change])
{
// number to be used for updation of
// lower, first values that will be used
// to construct the final number later
lower = value[(int)change];
upper = change;
suffix = "";
suf_init = true;
int len = (int)change;
while (len > 0) {
int k = (int)Math.sqrt(first[len]
+ 1);
suffix = suffix + (char)(k + 48);
len = len - first[len];
}
}
else if (lower == value[(int)change]) {
String tempsuf = "";
int len = (int)change;
while (len > 0) {
int k = (int)Math.sqrt(first[len]
+ 1);
tempsuf = tempsuf + (char)(k + 48);
len = len - first[len];
}
if ((tempsuf.compareTo(suffix) < 0)
|| (suf_init == false)) {
lower = value[(int)change];
upper = change;
suffix = tempsuf;
suf_init = true;
}
}
}
}
// check if number is found
if (found)
{
// construct the number from first values
long x = lower;
for (int i = 0; i < (n - x); i++)
answer += "1";
long temp = upper;
// fill in rest of the digits
while (temp > 0) {
int dig
= (int)Math.sqrt(first[(int)temp] + 1);
temp = temp - first[(int)temp];
answer += (char)(dig + '0');
}
return answer;
}
else
return "-1";
}
// Driver code
public static void main(String[] args)
{
// initialise N
int N = 2;
System.out.println(minValue(N));
}
}
// This code is contributed by Palak Gupta
Producción:
34
Complejidad de tiempo: O (81 * N)
Espacio auxiliar: O(81 * 10 5 )