Cuente números cuya suma máxima de suma de dígitos distintos sea menor o igual a M

Dada una array de enteros arr[] y un número M , la tarea es encontrar el recuento máximo de los números cuya suma de dígitos distintos es menor o igual que el número dado M .

Ejemplos: 

Entrada: arr[] = {1, 45, 16, 17, 219, 32, 22}, M = 10 
Salida: 3 
Explicación: 
la suma de dígitos de la array es: {1, 9, 7, 8, 12, 5 , 4} 
Suma máxima de sumas de dígitos distintos cuya suma menor que M es {1 + 5 + 4} 
Por lo tanto, la cuenta de tales números es 3.

Entrada: arr[] = {32, 45}, M = 2 
Salida: 0 
Explicación: 
La suma de dígitos de la array es – {5, 9} 
La suma máxima de la suma de dígitos distintos menos que M es 0 
Por lo tanto, el conteo de tales números es 0. 
 

Enfoque: 
La idea es encontrar la suma de dígitos de cada elemento en la array y luego ordenar la array de suma de dígitos.
Ahora el problema se reduce a contar el número de elementos de la array de suma de dígitos distintos ordenados, con una suma menor o igual a M. 
Para hacer esto, tome las sumas mínimas de dígitos distintos hasta que la suma de dichos números sea menor o igual a el número dado M y devolver la cuenta de tales números. 

Explicación con ejemplo:  

Given Array be - arr[] = {1, 45, 17, 32, 22}, M = 10

Then Digit-sum of each number in the array - 
Digit-sum(1) = 1
Digit-sum(45) = 4 + 5 = 9
Digit-sum(17) = 1 + 7 = 8
Digit-sum(32) = 3 + 2 = 5
Digit-sum(22) = 2 + 2 = 4

After sorting the digit-sum array - 
Digit-sum[] = {1, 4, 5, 8, 9}

Then there are three numbers such that, 
there sum is less than or equal to M = 10
which is {1, 4, 5} 
Sum = 1 + 4 + 5 = 10 ≤ M

Algoritmo:  

• Encuentre la suma de dígitos de cada elemento de la array y guárdela en otra array (digamos digit-sum[] )
• Ordene la array digit-sum[] en orden creciente.
• Elimine los elementos duplicados de la array de suma de dígitos ordenados [] de modo que solo haya una suma de dígitos única.
• Inicialice una suma variable a 0 para almacenar la suma actual.
• Itere sobre la array digit-sum[] y agregue los elementos a la suma hasta que el valor de la suma sea menor que igual a M e incremente el conteo.

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

// C++ implementation to find the
// Maximum count of numbers whose
// sum of distinct digit-sum less
// than or equal to the given number
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the
// digit-sum of a number
int SumofDigits(int digit)
{
    int sum = 0;
     
    // Loop to iterate the number
    // digit-wise to find digit-sum
    while (digit != 0) {
         
        // variable to store last digit
        int rem = digit % 10;
        sum += rem;
        digit /= 10;
    }
    return sum;
}
 
// Function to find the count of number
int findCountofNumbers(int arr[],
                   int n, int M){
     
    // Vector to store the Sum of Digits
    vector<int> SumDigits;
 
    // Sum of digits for each
    // element in vector
    for (int i = 0; i < n; i++) {
        int s = SumofDigits(arr[i]);
        SumDigits.push_back(s);
    }
 
    // Sorting the digitSum vector
    sort(SumDigits.begin(), SumDigits.end());
 
    // Removing the duplicate elements
    vector<int>::iterator ip;
    ip = unique(SumDigits.begin(),
                 SumDigits.end());
    SumDigits.resize(distance(
         SumDigits.begin(), ip)
         );
 
    // Count variable to store the Count
    int count = 0;
    int sum = 0;
    // Finding the Count of Numbers
    for (int i = 0; i < SumDigits.size(); i++) {
        if (sum > M)
            break;
        sum += SumDigits[i];
        if (sum <= M)
            count++;
    }
    return count;
}
 
// Driver Code
int main()
{
 
    int arr[] = { 1, 45, 16, 17,
           219, 32, 22 }, M = 10;
    int n = sizeof(arr) / sizeof(arr[0]);
 
    // Function Call
    cout << findCountofNumbers(arr, n, M);
    return 0;
}

# Python 3 implementation to find the
# Maximum count of numbers whose
# sum of distinct digit-sum less
# than or equal to the given number
 
# Function to find the
# digit-sum of a number
def SumofDigits( digit):
     
    sum = 0
     
    # Loop to iterate the number
    # digit-wise to find digit-sum
    while (digit != 0):
         
        # variable to store last digit
        rem = digit % 10
        sum += rem
        digit //= 10
     
    return sum
 
# Function to find the count of number
def findCountofNumbers(arr, n, M):
     
    # Vector to store the Sum of Digits
    SumDigits = []
 
    # Sum of digits for each
    # element in vector
    for i in range( n ):
        s = SumofDigits(arr[i])
        SumDigits.append(s)
 
    # Sorting the digitSum vector
    SumDigits.sort()
 
    # Removing the duplicate elements
    ip = list(set(SumDigits))
 
    # Count variable to store the Count
    count = 0
    sum = 0
     
    # Finding the Count of Numbers
    for i in range(len(SumDigits)):
        if (sum > M):
            break
        sum += SumDigits[i]
        if (sum <= M):
            count+=1
     
    return count
 
# Driver Code
if __name__ == "__main__":
 
    arr = [ 1, 45, 16, 17,
        219, 32, 22 ]
    M = 10
    n = len(arr)
 
    # Function Call
    print( findCountofNumbers(arr, n, M))
     
# This ccode is contributed by chitranayal

<script>
 
// Javascript implementation to find the
// Maximum count of numbers whose
// sum of distinct digit-sum less
// than or equal to the given number
 
// Function to find the
// digit-sum of a number
function SumofDigits(digit)
{
    let sum = 0;
       
    // Loop to iterate the number
    // digit-wise to find digit-sum
    while (digit != 0)
    {
         
        // Variable to store last digit
        let rem = digit % 10;
        sum += rem;
        digit = Math.floor(digit/10);
    }
    return sum;
}
 
// Function to find the count of number
function findCountofNumbers(arr, n, M)
{
     
    // Vector to store the Sum of Digits
    let SumDigits = [];
   
    // Sum of digits for each
    // element in vector
    for(let i = 0; i < n; i++)
    {
        let s = SumofDigits(arr[i]);
        SumDigits.push(s);
    }
   
    // Sorting the digitSum vector
    SumDigits.sort(function(a, b){return a - b;});
   
    // Removing the duplicate elements
    let ip = Array.from(new Set(SumDigits));
   
    // Count variable to store the Count
    let count = 0;
    let sum = 0;
     
    // Finding the Count of Numbers
    for(let i = 0; i < SumDigits.length; i++)
    {
        if (sum > M)
            break;
             
        sum += SumDigits[i];
         
        if (sum <= M)
            count++;
    }
    return count;
}
 
// Driver Code
let arr = [ 1, 45, 16, 17,
            219, 32, 22 ];
let M = 10;
let n = arr.length;
 
// Function Call
document.write(findCountofNumbers(arr, n, M));
 
// This code is contributed by avanitrachhadiya2155
 
</script>

3

Análisis de rendimiento: 

• Complejidad de tiempo: como en el enfoque dado, estamos usando una clasificación que toma O (NlogN) en el peor de los casos y para encontrar la suma de dígitos de cada elemento toma O (N * K) donde K es el número máximo de dígitos, Por lo tanto, la complejidad del tiempo será O(NlogN + N*k) .
• Espacio Auxiliar: O(N)