Dada suma de dígitos 
y suma de cuadrados de dígitos 
. Encuentre el número más pequeño con la suma de dígitos dada y la suma del cuadrado de los dígitos. El número no debe contener más de 100 dígitos. Escriba -1 si no existe tal número o si el número de dígitos es mayor a 100.
Ejemplos:
Entrada: a = 18, b = 162
Salida: 99
Explicación: 99 es el número más pequeño posible cuya suma de dígitos = 9 + 9 = 18 y suma de cuadrados de dígitos es 9 2 +9 2 = 162.
Entrada: a = 12 , b = 9
Salida : -1
Enfoque:
Dado que el número más pequeño puede tener 100 dígitos, no se puede almacenar. Por lo tanto, el primer paso para resolverlo será encontrar el número mínimo de dígitos que nos puede dar la suma de dígitos como y la suma del cuadrado de dígitos como . Para encontrar el número mínimo de dígitos, podemos usar la programación dinámica. DP[a][b] significa el número mínimo de dígitos en un número cuya suma de los dígitos será y la suma del cuadrado de los dígitos será . Si no existe tal número entonces DP[a][b] será -1.
Dado que el número no puede exceder los 100 dígitos, la array DP tendrá un tamaño de 101*8101 . Iterar para cada dígito y probar todas las combinaciones posibles de dígitos que nos den la suma de los dígitos como y la suma del cuadrado de los dígitos como . Almacene el número mínimo de dígitos en DP[a][b] usando la siguiente relación de recurrencia:
DP[a][b] = min(númeromínimoDeDígitos(a – i, b – (i * i)) + 1 )
donde 1<=i<=9
Después de obtener el número mínimo de dígitos, encuentre los dígitos. Para encontrar los dígitos, verifique todas las combinaciones e imprima los dígitos que satisfagan la siguiente condición:
1 + dp[a – i][b – i * i] == dp[a][b]
donde 1<=i<=9
Si cualquiera de i cumple la condición anterior, reduzca por i y por i*i y rompa. Continúe repitiendo el proceso anterior para encontrar todos los dígitos hasta que sea 0 y sea 0.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to find the Smallest number with given sum of
// digits and sum of square of digits
#include <bits/stdc++.h>
using namespace std;
int dp[901][8101];
// Top down dp to find minimum number of digits with given
// sum of digits a and sum of square of digits as b
int minimumNumberOfDigits(int a, int b)
{
// Invalid condition
if (a > b || a < 0 || b < 0 || a > 900 || b > 8100)
return -1;
// Number of digits satisfied
if (a == 0 && b == 0)
return 0;
// Memoization
if (dp[a][b] != -1)
return dp[a][b];
// Initialize ans as maximum as we have to find the
// minimum number of digits
int ans = 101;
// Check for all possible combinations of digits
for (int i = 9; i >= 1; i--) {
// recurrence call
int k = minimumNumberOfDigits(a - i, b - (i * i));
// If the combination of digits cannot give sum as a
// and sum of square of digits as b
if (k != -1)
ans = min(ans, k + 1);
}
// Returns the minimum number of digits
return dp[a][b] = ans;
}
// Function to print the digits that gives
// sum as a and sum of square of digits as b
void printSmallestNumber(int a, int b)
{
// initialize the dp array as -1
memset(dp, -1, sizeof(dp));
// base condition
dp[0][0] = 0;
// function call to get the minimum number of digits
int k = minimumNumberOfDigits(a, b);
// When there does not exists any number
if (k == -1 || k > 100)
cout << "-1";
else {
// Printing the digits from the most significant
// digit
while (a > 0 && b > 0) {
// Trying all combinations
for (int i = 1; i <= 9; i++) {
// checking conditions for minimum digits
if (a >= i && b >= i * i
&& 1 + dp[a - i][b - i * i] == dp[a][b]) {
cout << i;
a -= i;
b -= i * i;
break;
}
}
}
}
}
// Driver Code
int main()
{
int a = 18, b = 162;
// Function call to print the smallest number
printSmallestNumber(a, b);
}
C
// C program to find the Smallest number with given sum of
// digits and sum of square of digits
#include <stdio.h>
#include <string.h>
// Find minimum between two numbers.
int min(int num1, int num2)
{
return (num1 > num2) ? num2 : num1;
}
int dp[901][8101];
// Top down dp to find minimum number of digits with given
// sum of digits a and sum of square of digits as b
int minimumNumberOfDigits(int a, int b)
{
// Invalid condition
if (a > b || a < 0 || b < 0 || a > 900 || b > 8100)
return -1;
// Number of digits satisfied
if (a == 0 && b == 0)
return 0;
// Memoization
if (dp[a][b] != -1)
return dp[a][b];
// Initialize ans as maximum as we have to find the
// minimum number of digits
int ans = 101;
// Check for all possible combinations of digits
for (int i = 9; i >= 1; i--) {
// recurrence call
int k = minimumNumberOfDigits(a - i, b - (i * i));
// If the combination of digits cannot give sum as a
// and sum of square of digits as b
if (k != -1)
ans = min(ans, k + 1);
}
// Returns the minimum number of digits
return dp[a][b] = ans;
}
// Function to print the digits that gives
// sum as a and sum of square of digits as b
void printSmallestNumber(int a, int b)
{
// initialize the dp array as -1
memset(dp, -1, sizeof(dp));
// base condition
dp[0][0] = 0;
// function call to get the minimum number of digits
int k = minimumNumberOfDigits(a, b);
// When there does not exists any number
if (k == -1 || k > 100)
printf("-1");
else {
// Printing the digits from the most significant
// digit
while (a > 0 && b > 0) {
// Trying all combinations
for (int i = 1; i <= 9; i++) {
// checking conditions for minimum digits
if (a >= i && b >= i * i
&& 1 + dp[a - i][b - i * i]
== dp[a][b]) {
printf("%d", i);
a -= i;
b -= i * i;
break;
}
}
}
}
}
// Driver Code
int main()
{
int a = 18, b = 162;
// Function call to print the smallest number
printSmallestNumber(a, b);
}
// This code is contributed by Sania Kumari Gupta
Java
import java.util.Arrays;
// Java program to find the Smallest number
// with given sum of digits and
// sum of square of digits
class GFG {
static int dp[][] = new int[901][8101];
// Top down dp to find minimum number of digits with
// given sum of digits a and sum of square of digits as b
static int minimumNumberOfDigits(int a, int b) {
// Invalid condition
if (a > b || a < 0 || b < 0 || a > 900 || b > 8100) {
return -1;
}
// Number of digits satisfied
if (a == 0 && b == 0) {
return 0;
}
// Memoization
if (dp[a][b] != -1) {
return dp[a][b];
}
// Initialize ans as maximum as we have to find the
// minimum number of digits
int ans = 101;
// Check for all possible combinations of digits
for (int i = 9; i >= 1; i--) {
// recurrence call
int k = minimumNumberOfDigits(a - i, b - (i * i));
// If the combination of digits cannot give sum as a
// and sum of square of digits as b
if (k != -1) {
ans = Math.min(ans, k + 1);
}
}
// Returns the minimum number of digits
return dp[a][b] = ans;
}
// Function to print the digits that gives
// sum as a and sum of square of digits as b
static void printSmallestNumber(int a, int b) {
// initialize the dp array as -1
for (int[] row : dp) {
Arrays.fill(row, -1);
}
// base condition
dp[0][0] = 0;
// function call to get the minimum number of digits
int k = minimumNumberOfDigits(a, b);
// When there does not exists any number
if (k == -1 || k > 100) {
System.out.println("-1");
} else {
// Printing the digits from the most significant digit
while (a > 0 && b > 0) {
// Trying all combinations
for (int i = 1; i <= 9; i++) {
// checking conditions for minimum digits
if (a >= i && b >= i * i
&& 1 + dp[a - i][b - i * i] == dp[a][b]) {
System.out.print(i);
a -= i;
b -= i * i;
break;
}
}
}
}
}
// Driver Code
public static void main(String args[]) {
int a = 18, b = 162;
// Function call to print the smallest number
printSmallestNumber(a, b);
}
}
// This code is contributed by PrinciRaj19992
Python3
# Python3 program to find the Smallest number # with given sum of digits and # sum of square of digits dp=[[-1 for i in range(8101)]for i in range(901)] # Top down dp to find minimum number of digits with # given sum of digits a and sum of square of digits as b def minimumNumberOfDigits(a,b): # Invalid condition if (a > b or a < 0 or b < 0 or a > 900 or b > 8100): return -1 # Number of digits satisfied if (a == 0 and b == 0): return 0 # Memoization if (dp[a][b] != -1): return dp[a][b] # Initialize ans as maximum as we have to find the # minimum number of digits ans = 101 #Check for all possible combinations of digits for i in range(9,0,-1): # recurrence call k = minimumNumberOfDigits(a - i, b - (i * i)) # If the combination of digits cannot give sum as a # and sum of square of digits as b if (k != -1): ans = min(ans, k + 1) # Returns the minimum number of digits dp[a][b] = ans return ans # Function to print the digits that gives # sum as a and sum of square of digits as b def printSmallestNumber(a,b): # initialize the dp array as for i in range(901): for j in range(8101): dp[i][j]=-1 # base condition dp[0][0] = 0 # function call to get the minimum number of digits k = minimumNumberOfDigits(a, b) # When there does not exists any number if (k == -1 or k > 100): print(-1,end='') else: # Printing the digits from the most significant digit while (a > 0 and b > 0): # Trying all combinations for i in range(1,10): #checking conditions for minimum digits if (a >= i and b >= i * i and 1 + dp[a - i][b - i * i] == dp[a][b]): print(i,end='') a -= i b -= i * i break # Driver Code if __name__=='__main__': a = 18 b = 162 # Function call to print the smallest number printSmallestNumber(a,b) # This code is contributed by sahilshelangia
C#
// C# program to find the Smallest number
// with given sum of digits and
// sum of square of digits
using System;
public class GFG {
static int [,]dp = new int[901,8101];
// Top down dp to find minimum number of digits with
// given sum of digits a and sum of square of digits as b
static int minimumNumberOfDigits(int a, int b) {
// Invalid condition
if (a > b || a < 0 || b < 0 || a > 900 || b > 8100) {
return -1;
}
// Number of digits satisfied
if (a == 0 && b == 0) {
return 0;
}
// Memoization
if (dp[a,b] != -1) {
return dp[a,b];
}
// Initialize ans as maximum as we have to find the
// minimum number of digits
int ans = 101;
// Check for all possible combinations of digits
for (int i = 9; i >= 1; i--) {
// recurrence call
int k = minimumNumberOfDigits(a - i, b - (i * i));
// If the combination of digits cannot give sum as a
// and sum of square of digits as b
if (k != -1) {
ans = Math.Min(ans, k + 1);
}
}
// Returns the minimum number of digits
return dp[a,b] = ans;
}
// Function to print the digits that gives
// sum as a and sum of square of digits as b
static void printSmallestNumber(int a, int b) {
// initialize the dp array as -1
for (int i = 0; i < dp.GetLength(0); i++)
for (int j = 0; j < dp.GetLength(1); j++)
dp[i, j] = -1;
// base condition
dp[0,0] = 0;
// function call to get the minimum number of digits
int k = minimumNumberOfDigits(a, b);
// When there does not exists any number
if (k == -1 || k > 100) {
Console.WriteLine("-1");
} else {
// Printing the digits from the most significant digit
while (a > 0 && b > 0) {
// Trying all combinations
for (int i = 1; i <= 9; i++) {
// checking conditions for minimum digits
if (a >= i && b >= i * i
&& 1 + dp[a - i,b - i * i] == dp[a,b]) {
Console.Write(i);
a -= i;
b -= i * i;
break;
}
}
}
}
}
// Driver Code
public static void Main() {
int a = 18, b = 162;
// Function call to print the smallest number
printSmallestNumber(a, b);
}
}
// This code is contributed by PrinciRaj19992
Javascript
<script>
// JavaScript program to find the Smallest number
// with given sum of digits and
// sum of square of digits
// initialize the dp array as -1
dp = new Array(901).fill(-1).map(() =>
new Array(8101).fill(-1));;
// Top down dp to find minimum
// number of digits with
// given sum of digits a and
// sum of square of digits as b
function minimumNumberOfDigits(a, b)
{
// Invalid condition
if (a > b || a < 0 || b < 0 || a > 900 || b > 8100)
return -1;
// Number of digits satisfied
if (a == 0 && b == 0)
return 0;
// Memoization
if (dp[a][b] != -1)
return dp[a][b];
// Initialize ans as maximum as we have to find the
// minimum number of digits
var ans = 101;
// Check for all possible combinations of digits
for (var i = 9; i >= 1; i--) {
// recurrence call
var k = minimumNumberOfDigits(a - i, b - (i * i));
// If the combination of digits cannot give sum as a
// and sum of square of digits as b
if (k != -1)
ans = Math.min(ans, k + 1);
}
// Returns the minimum number of digits
return dp[a][b] = ans;
}
// Function to print the digits that gives
// sum as a and sum of square of digits as b
function printSmallestNumber(a, b)
{
// base condition
dp[0][0] = 0;
// function call to get the
// minimum number of digits
var k = minimumNumberOfDigits(a, b);
// When there does not exists any number
if (k == -1 || k > 100)
document.write( "-1");
else {
// Printing the digits from the
// most significant digit
while (a > 0 && b > 0) {
// Trying all combinations
for (var i = 1; i <= 9; i++) {
// checking conditions for minimum digits
if (a >= i && b >= i * i &&
1 + dp[a - i][b - i * i] == dp[a][b]) {
document.write( i);
a -= i;
b -= i * i;
break;
}
}
}
}
}
var a = 18, b = 162;
// Function call to print the smallest number
printSmallestNumber(a,b);
// This code is contributed by SoumikMondal
</script>
Producción:
99
Complejidad del tiempo : O(900*8100*9)
Espacio auxiliar : O(900*8100)
Nota: La complejidad del tiempo está en términos de números, ya que estamos probando todas las combinaciones posibles de dígitos.
Publicación traducida automáticamente
Artículo escrito por SHUBHAMGUPTA26 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA