Given a positive integer K, and an array arr[] consisting of N( =9) integers such that arr[i] represents the cost of the digit (i+1), the task is to find the largest number that can be formed using the digits over the range [1, 9] such that the sum of the cost of digits of the number formed is K.
Examples:
Input: K = 14, arr[] = {3, 12, 9, 5, 3, 4, 6, 5, 10}
Output: 8555
Explanation:
One possible number with cost K that can be formed is, 8555. The cost of including digit 8 is arr[7]( =5) and digit 5 is arr[2]( =3).
Therefore, the total cost is (5+3*3 = 14). And ialso the number formed 8555 is the maximum possible number with this cost.Input: K = 5, arr[] = {3, 12, 9, 5, 3, 4, 6, 5, 10}
Output: 8
Explanation:
One possible number with cost K that can be formed is, 8. The cost of including digit 8 is arr[7]( =5).
Therefore, the total cost is (5 = 5). And ialso the number formed 8 is the maximum possible number with this cost.
Approach: The given problem can be solved based on the following observations:
- The problem is the variation of the 0/1 Unbounded Knapsack as the digits chosen to form the largest number can also be repeated and their sum of costs must be K.
- Hence, the idea is to either include or exclude every possible digit repeatedly to form the largest number and print the maximum number obtained after all possible combinations.
- The above idea can be implemented according to the following recurrence relation:
- Keep track of the digit used to form the number and the remaining sum K at each step.
- The base condition of the recurrence relation is:
- If the sum K becomes 0, then this results in one of the combinations of the numbers formed.
- If K is negative or all the array is traversed, then it is impossible to form any number whose sum of costs is K.
- At each step, first, include and then exclude any digit D and recursively call for the function, with the updated remaining cost K respectively.
Follow the steps below to solve the given problem:
- Initialize 2D array say dp[][] of size 10*K such that dp[i][j] stores the largest number formed by using the first i digits having the sum j.
- Define a recursive function, say recursion(i, K) where starting index, the sum K, and performs the following steps:
- Define the base case as:
- If the value of the sum K becomes 0, then return an empty string from the function as the number whose sum of the cost of digit has been formed.
- If the value of the sum K is less than 0 or i is equal to N, then return “0” from the function as no number can be formed.
- If the current state dp[i][N] is already calculated, then return this value from the function.
- Store the result obtained by including the current digit i+1 as to_string(i+1) + recursion(0, K – arr[D]) in the variable, say include.
- Store the result obtained by excluding the current digit i+1 as recursion(i+1, K – arr[D]) in the variable, say exclude.
- Define the base case as:
- Update the current DP state dp[i][K] to max(include, exclude) and return this value from the function.
- After completing the above steps, call the recursive function recursion(0, K) and check if the string returned is empty, then print “0”. Otherwise, print the returned string as the resultant maximum number formed.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include "bits/stdc++.h"using namespace std;// Function to find the maximum number// among the two numbers S and Tstring getMaximum(string& S, string& T){ // If "0" exists in the string S if (S.find("0") != string::npos) return T; // If "0" exists in the string T if (T.find("0") != string::npos) return S; // Else return the maximum number // formed return (S.length() > T.length() ? S : T);}// Recursive function to find maximum// number formed such that the sum of// cost of digits of formed number is Kstring recursion(int arr[], int idx, int N, int K, vector<vector<string> >& dp){ // Base Case if (K == 0) { return ""; } if (K < 0 or idx == N) { return "0"; } // Return the stored state if (dp[idx][K] != "-1") return dp[idx][K]; // Including the digit (idx + 1) string include = to_string(idx + 1) + recursion(arr, 0, N, K - arr[idx], dp); // Excluding the digit (idx + 1) string exclude = recursion( arr, idx + 1, N, K, dp); // Store the result and return return dp[idx][K] = getMaximum( include, exclude);}// Function to find the maximum number// formed such that the sum of the cost// digits in the formed number is Kstring largestNumber(int arr[], int N, int K){ // Stores all Dp-states vector<vector<string> > dp( N + 1, vector<string>(K + 1, "-1")); // Recursive Call string ans = recursion(arr, 0, N, K, dp); // Return the result return (ans == "" ? "0" : ans);}// Driver Codeint main(){ int arr[] = { 3, 12, 9, 5, 3, 4, 6, 5, 10 }; int K = 14; int N = sizeof(arr) / sizeof(arr[0]); cout << largestNumber(arr, N, K); return 0;} |
Java
// Java program for the above approachimport java.util.*;public class Main{ // Function to find the maximum number // among the two numbers S and T static String getMaximum(String S, String T) { // If "0" exists in the string S if (S.indexOf("0") > -1) return T; // If "0" exists in the string T if (T.indexOf("0") > -1) return S; // Else return the maximum number // formed return S.length() > T.length() ? S : T; } // Recursive function to find maximum // number formed such that the sum of // cost of digits of formed number is K static String recursion(int[] arr, int idx, int N, int K, Vector<Vector<String>> dp) { // Base Case if (K == 0) { return ""; } if (K < 0 || idx == N) { return "0"; } // Return the stored state if (dp.get(idx).get(K) != "-1") return dp.get(idx).get(K); // Including the digit (idx + 1) String include = String.valueOf(idx + 1) + recursion(arr, 0, N, K - arr[idx], dp); // Excluding the digit (idx + 1) String exclude = recursion(arr, idx + 1, N, K, dp); // Store the result and return dp.get(idx).set(K, getMaximum(include, exclude)); return dp.get(idx).get(K); } // Function to find the maximum number // formed such that the sum of the cost // digits in the formed number is K static String largestNumber(int[] arr, int N, int K) { // Stores all Dp-states Vector<Vector<String>> dp = new Vector<Vector<String>>(); for(int i = 0; i < N + 1; i++) { dp.add(new Vector<String>()); for(int j = 0; j < K + 1; j++) { dp.get(i).add("-1"); } } // Recursive Call String ans = recursion(arr, 0, N, K, dp); // Return the result return ans == "" ? "0" : ans; } public static void main(String[] args) { int[] arr = {3, 12, 9, 5, 3, 4, 6, 5, 10}; int K = 14; int N = arr.length; System.out.print(largestNumber(arr, N, K)); }}// This code is contributed by decode2207. |
Python3
# Python program for the above approach# Function to find the maximum number# among the two numbers S and Tdef getMaximum(S, T): # If "0" exists in the string S if (S.count("0") > 0): return T; # If "0" exists in the string T if (T.count("0") > 0): return S; # Else return the maximum number # formed return S if len(S) > len(T) else T;# Recursive function to find maximum# number formed such that the sum of# cost of digits of formed number is Kdef recursion(arr, idx, N, K, dp): # Base Case if (K == 0): return ""; if (K < 0 or idx == N): return "0"; # Return the stored state if (dp[idx][K] != "-1"): return dp[idx][K]; # Including the digit (idx + 1) include = str(idx + 1) + recursion(arr, 0, N, K - arr[idx], dp); # Excluding the digit (idx + 1) exclude = recursion(arr, idx + 1, N, K, dp); # Store the result and return dp[idx][K] = getMaximum(include, exclude) return (dp[idx][K])# Function to find the maximum number# formed such that the sum of the cost# digits in the formed number is Kdef largestNumber(arr, N, K): # Stores all Dp-states dp = [["-1" for i in range(K + 1)] for i in range(N + 1)] # Recursive Call ans = recursion(arr, 0, N, K, dp); # Return the result return "0" if ans == "" else ans;# Driver Codearr = [3, 12, 9, 5, 3, 4, 6, 5, 10];K = 14;N = len(arr);print(largestNumber(arr, N, K));# This code is contributed by _saurabh_jaiswal. |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG { // Function to find the maximum number // among the two numbers S and T static string getMaximum(string S, string T) { // If "0" exists in the string S if (S.IndexOf("0") > -1) return T; // If "0" exists in the string T if (T.IndexOf("0") > -1) return S; // Else return the maximum number // formed return (S.Length > T.Length ? S : T); } // Recursive function to find maximum // number formed such that the sum of // cost of digits of formed number is K static string recursion(int[] arr, int idx, int N, int K, List<List<string>> dp) { // Base Case if (K == 0) { return ""; } if (K < 0 || idx == N) { return "0"; } // Return the stored state if (dp[idx][K] != "-1") return dp[idx][K]; // Including the digit (idx + 1) string include = (idx + 1).ToString() + recursion(arr, 0, N, K - arr[idx], dp); // Excluding the digit (idx + 1) string exclude = recursion(arr, idx + 1, N, K, dp); // Store the result and return return dp[idx][K] = getMaximum(include, exclude); } // Function to find the maximum number // formed such that the sum of the cost // digits in the formed number is K static string largestNumber(int[] arr, int N, int K) { // Stores all Dp-states List<List<string>> dp = new List<List<string>>(); for(int i = 0; i < N + 1; i++) { dp.Add(new List<string>()); for(int j = 0; j < K + 1; j++) { dp[i].Add("-1"); } } // Recursive Call string ans = recursion(arr, 0, N, K, dp); // Return the result return (ans == "" ? "0" : ans); } static void Main() { int[] arr = {3, 12, 9, 5, 3, 4, 6, 5, 10}; int K = 14; int N = arr.Length; Console.Write(largestNumber(arr, N, K)); }}// This code is contributed by divyesh072019. |
Javascript
<script>// Javascript program for the above approach// Function to find the maximum number// among the two numbers S and Tfunction getMaximum(S, T) { // If "0" exists in the string S if (S.indexOf("0") > -1) return T; // If "0" exists in the string T if (T.indexOf("0") > -1) return S; // Else return the maximum number // formed return S.length > T.length ? S : T;}// Recursive function to find maximum// number formed such that the sum of// cost of digits of formed number is Kfunction recursion(arr, idx, N, K, dp){ // Base Case if (K == 0) { return ""; } if (K < 0 || idx == N) { return "0"; } // Return the stored state if (dp[idx][K] != "-1") return dp[idx][K]; // Including the digit (idx + 1) let include = String(idx + 1) + recursion(arr, 0, N, K - arr[idx], dp); // Excluding the digit (idx + 1) let exclude = recursion(arr, idx + 1, N, K, dp); // Store the result and return return (dp[idx][K] = getMaximum(include, exclude));}// Function to find the maximum number// formed such that the sum of the cost// digits in the formed number is Kfunction largestNumber(arr, N, K){ // Stores all Dp-states let dp = new Array(N + 1).fill(0).map(() => new Array(K + 1).fill(-1)); // Recursive Call let ans = recursion(arr, 0, N, K, dp); // Return the result return ans == "" ? "0" : ans;}// Driver Codelet arr = [3, 12, 9, 5, 3, 4, 6, 5, 10];let K = 14;let N = arr.length;document.write(largestNumber(arr, N, K));// This code is contributed by _saurabh_jaiswal.</script> |
Output:
8555
Time Complexity: O(9*K2)
Auxiliary Space: O(9*K)
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!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
