Números mínimos deci-binarios requeridos para obtener una suma dada S

Dada una string numérica S que representa un entero decimal positivo, la tarea es encontrar el número mínimo de números deci-binarios positivos necesarios para obtener la suma S.

Números deci-binarios: Números decimales que consisten en solo 0 s y 1 s como sus dígitos. 
 

Ejemplos:

Entrada: S = “31”
Salida: 3
Explicación: S se puede representar como la suma de un mínimo de 3 números deci-binarios {10, 10, 11}.

Entrada: S = “82734”
Salida: 8
Explicación: S se puede representar como la suma mínima de 8 números deci-binarios {11111, 11111, 10111, 10101, 10100, 10100, 10100, 10000}.

Enfoque: El problema dado se puede resolver con base en las siguientes observaciones: 

Supongamos que se necesitan X números deci-binarios para obtener la suma S. Para hacer que la suma de X números Deci-Binarios en el i-ésimo lugar sea igual a un dígito d en S , debe haber exactamente d números Deci-Binarios entre X números que tengan 1 en la i-ésima posición. 
Por lo tanto, el número mínimo de números Deci-Binarios necesarios para obtener una suma S es igual al valor máximo de cualquiera de los dígitos de S .

Por lo tanto, para resolver el problema, itere sobre los caracteres de la string S y encuentre el dígito máximo presente en ella.

A continuación se muestra la implementación del enfoque anterior:

// 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 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 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# 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

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

3

Complejidad temporal: O(N)
Espacio auxiliar: O(N)