Minimum Deci-Binary numbers required to obtain a given sum S

0 1 3 minutes read

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 S
int 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 Code
int main()
{
 
    string S = "31";
    cout << minimum_deci_binary_number(S);
 
    return 0;
}

Java

// Java program to implement
// the above approach
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 = 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 Code
public 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 S
def 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 Code
if __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 approach
using 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 S
function 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>

Output

Time Complexity: O(N)
Auxiliary Space: O(1)

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 zambiatek!