Given a numeric string S representing a positive decimal integer, the task is to find the minimum number of positive Deci-Binary numbers required to obtain the sum S.
Deci-Binary Numbers: Decimal numbers consisting of only 0s and 1s as its digits.
Examples:
Input: S = “31”
Output: 3
Explanation: S can be represented as the sum of minimum of 3 Deci-Binary numbers {10, 10, 11}.Input: S = “82734”
Output: 8
Explanation: S can be represented as sum minimum of 8 Deci-Binary numbers {11111, 11111, 10111, 10101, 10100, 10100, 10100, 10000}.
Approach: The given problem can be solved based on the following observations:
Suppose X Deci-Binary numbers are needed to obtain the sum S. To make the sum of X Deci-Binary numbers at i-th place equal to a digit d in S, there must be exactly d Deci-Binary numbers among X numbers having 1 at the ith position.
Therefore, the minimum number of Deci-Binary numbers required to obtain a sum S is equal to the maximum value of any of the digits of S.
Therefore, to solve the problem, iterate over the characters of the string S and find the maximum digit present in it.
Below is the implementation of the above approach:
C++
// C++ Program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to find the count of minimum// Deci-Binary numbers required to obtain Sint minimum_deci_binary_number(string s){ // Stores the minimum count int m = INT_MIN; // Iterate over the string s for (int i = 0; i < s.size(); i++) { // Convert the char to its // equivalent integer int temp = s[i] - '0'; // If current character is // the maximum so far if (temp > m) { // Update the maximum digit m = temp; } } // Print the required result return m;}// Driver Codeint main(){ string S = "31"; cout << minimum_deci_binary_number(S); return 0;} |
Java
// Java program to implement// the above approachclass GFG{ // Function to find the count of minimum// Deci-Binary numbers required to obtain Sstatic int minimum_deci_binary_number(String s){ // Stores the minimum count int m = Integer.MIN_VALUE; // Iterate over the string s for(int i = 0; i < s.length(); i++) { // Convert the char to its // equivalent integer int temp = s.charAt(i) - '0'; // If current character is // the maximum so far if (temp > m) { // Update the maximum digit m = temp; } } // Print the required result return m;}// Driver Codepublic static void main (String[] args){ String S = "31"; System.out.println(minimum_deci_binary_number(S));}}// This code is contributed by AnkThon |
Python3
# Python3 Program to implement# the above approach# Function to find the count of minimum# Deci-Binary numbers required to obtain Sdef minimum_deci_binary_number(s): # Stores the minimum count m = -10**19 # Iterate over the string s for i in range(len(s)): # Convert the char to its # equivalent integer temp = ord(s[i]) - ord('0') # If current character is # the maximum so far if (temp > m): # Update the maximum digit m = temp # Print required result return m# Driver Codeif __name__ == '__main__': S = "31" print(minimum_deci_binary_number(S))# This code is contributed by mohit kumar 29 |
C#
// C# program to implement// the above approachusing System;class GFG{ // Function to find the count of minimum // Deci-Binary numbers required to obtain S static int minimum_deci_binary_number(string s) { // Stores the minimum count int m = int.MinValue; // Iterate over the string s for(int i = 0; i < s.Length; i++) { // Convert the char to its // equivalent integer int temp = s[i] - '0'; // If current character is // the maximum so far if (temp > m) { // Update the maximum digit m = temp; } } // Print the required result return m; } // Driver Code public static void Main (String[] args) { string S = "31"; Console.WriteLine(minimum_deci_binary_number(S)); }}// This code is contributed by AnkThon |
Javascript
<script>// JavaScript program to implement// the above approach// Function to find the count of minimum// Deci-Binary numbers required to obtain Sfunction minimum_deci_binary_number(s){ // Stores the minimum count let m = Number.MIN_VALUE; // Iterate over the string s for(let i = 0; i < s.length; i++) { // Convert the char to its // equivalent integer let temp = s[i] - '0'; // If current character is // the maximum so far if (temp > m) { // Update the maximum digit m = temp; } } // Print the required result return m;} // Driver code let S = "31"; document.write(minimum_deci_binary_number(S));</script> |
3
Time Complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!