Smallest number with given sum of digits and sum of square of digits

22 August 2024

0

Given the sum of digits a and sum of the square of digits b . Find the smallest number with the given sum of digits and the sum of the square of digits. The number should not contain more than 100 digits. Print -1 if no such number exists or if the number of digits is more than 100.
Examples:

Input : a = 18, b = 162
Output : 99
Explanation : 99 is the smallest possible number whose sum of digits = 9 + 9 = 18 and sum of squares of digits is 9²+9² = 162.
Input : a = 12, b = 9
Output : -1

Approach:
Since the smallest number can be of 100 digits, it cannot be stored. Hence the first step to solve it will be to find the minimum number of digits which can give us the sum of digits as $a$ and sum of the square of digits as $b$ . To find the minimum number of digits, we can use Dynamic Programming. DP[a][b] signifies the minimum number of digits in a number whose sum of the digits will be $a$ and sum of the square of digits will be $b$ . If there does not exist any such number then DP[a][b] will be -1.
Since the number cannot exceed 100 digits, DP array will be of size 101*8101. Iterate for every digit, and try all possible combination of digits which gives us the sum of digits as $a$ and sum of the square of digits as $b$ . Store the minimum number of digits in DP[a][b] using the below recurrence relation:

DP[a][b] = min( minimumNumberOfDigits(a – i, b – (i * i)) + 1 )
where 1<=i<=9

After getting the minimum number of digits, find the digits. To find the digits, check for all combinations and print those digits which satisfies the condition below:

1 + dp[a – i][b – i * i] == dp[a][b]
where 1<=i<=9

If the condition above is met by any of i, reduce a by i and b by i*i and break. Keep on repeating the above process to find all the digits till a is 0 and b is 0.

Below is the implementation of the above approach:

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>

Output

Time Complexity : O(900*8100*9)
Auxiliary Space : O(900*8100)

Efficient approach : Using DP Tabulation method ( Iterative approach )

The approach to solve this problem is same but DP tabulation(bottom-up) method is better then Dp + memoization(top-down) because memoization method needs extra stack space of recursion calls.

Implementation :

C++

// C++ code for the above approach
#include <cstring>
#include <iostream>
using namespace std;
 
int dp[901][8101];
 
// function 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)
{
    // base case
    if (a > b || a < 0 || b < 0 || a > 900 || b > 8100)
        return -1;
 
    if (a == 0 && b == 0)
        return 0;
 
    // initialize Dp with -1
    memset(dp, -1, sizeof(dp));
 
    // Base Case
    dp[0][0] = 0;
 
    // iterating over subproblems to get the current
    // solution of dp from previous computations
    for (int i = 0; i <= a; i++) {
        for (int j = 0; j <= b; j++) {
            if (dp[i][j] == -1)
                continue;
 
            for (int digit = 1; digit <= 9; digit++) {
                if (i + digit <= a
                    && j + digit * digit <= b) {
                    int new_a = i + digit;
                    int new_b = j + digit * digit;
 
                    if (dp[new_a][new_b] == -1
                        || dp[new_a][new_b] > dp[i][j] + 1)
                        dp[new_a][new_b] = dp[i][j] + 1;
                }
            }
        }
    }
 
    // return answer
    return dp[a][b];
}
 
// Function to print the digits that gives
// sum as a and sum of square of digits as b
void printSmallestNumber(int a, int b)
{
    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 digit = 1; digit <= 9; digit++) {
                // checking conditions for minimum digits
                if (a >= digit && b >= digit * digit
                    && dp[a][b]
                           == dp[a - digit]
                                [b - digit * digit]
                                  + 1) {
                    cout << digit;
                    a -= digit;
                    b -= digit * digit;
                    break;
                }
            }
        }
    }
}
 
// Driver Code
int main()
{
    int a = 18, b = 162;
    printSmallestNumber(a, b);
    return 0;
}

C#

using System;
 
class Program {
    static int[, ] dp = new int[901, 8101];
 
    // Function to find the minimum number of digits with a
    // given sum of digits a and sum of squares of digits as
    // b
    static int MinimumNumberOfDigits(int a, int b)
    {
        // Base case
        if (a > b || a < 0 || b < 0 || a > 900 || b > 8100)
            return -1;
 
        if (a == 0 && b == 0)
            return 0;
 
        // Initialize dp with -1
        for (int i = 0; i < 901; i++) {
            for (int j = 0; j < 8101; j++) {
                dp[i, j] = -1;
            }
        }
 
        // Base Case
        dp[0, 0] = 0;
 
        // Iterating over subproblems to get the current
        // solution of dp from previous computations
        for (int i = 0; i <= a; i++) {
            for (int j = 0; j <= b; j++) {
                if (dp[i, j] == -1)
                    continue;
 
                for (int digit = 1; digit <= 9; digit++) {
                    if (i + digit <= a
                        && j + digit * digit <= b) {
                        int newA = i + digit;
                        int newB = j + digit * digit;
 
                        if (dp[newA, newB] == -1
                            || dp[newA, newB]
                                   > dp[i, j] + 1)
                            dp[newA, newB] = dp[i, j] + 1;
                    }
                }
            }
        }
 
        // Return the answer
        return dp[a, b];
    }
 
    // Function to print the digits that give a sum as a and
    // sum of the square of digits as b
    static void PrintSmallestNumber(int a, int b)
    {
        int k = MinimumNumberOfDigits(a, b);
 
        // When there does not exist 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 digit = 1; digit <= 9; digit++) {
                    // Checking conditions for the minimum
                    // digits
                    if (a >= digit && b >= digit * digit
                        && dp[a, b]
                               == dp[a - digit,
                                     b - digit * digit]
                                      + 1) {
                        Console.Write(digit);
                        a -= digit;
                        b -= digit * digit;
                        break;
                    }
                }
            }
        }
    }
 
    static void Main(string[] args)
    {
        int a = 18, b = 162;
        PrintSmallestNumber(a, b);
    }
}

Output

Time Complexity : O(900*8100*9)
Auxiliary Space : O(900*8100)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

Smallest number with given sum of digits and sum of square of digits

C++

C

Java

Python3

C#

Javascript

C++

C#

Java Program for Longest Common Subsequence

Maximum height of Tree when any Node can be considered as Root

Print Fibonacci sequence using 2 variables

LEAVE A REPLY Cancel reply

Most Popular

Vietnam’s Success in Software Outsourcing

Install Python 3 / Python 2.7 on Rocky Linux 8 |AlmaLinux 8

How To Manage Angular JS Projects using Angular CLI

How To Install PHP 8.2 on Ubuntu 22.04|20.04|18.04

Recent Comments

EDITOR PICKS

Vietnam’s Success in Software Outsourcing

Install Python 3 / Python 2.7 on Rocky Linux 8 |AlmaLinux 8

How To Manage Angular JS Projects using Angular CLI

POPULAR POSTS

Vietnam’s Success in Software Outsourcing

Install Python 3 / Python 2.7 on Rocky Linux 8 |AlmaLinux 8

How To Manage Angular JS Projects using Angular CLI

POPULAR CATEGORY

ABOUT US

FOLLOW US