Cuente números con exactamente K dígitos distintos de cero y sumas de dígitos impares distintas

Dado un número entero N y un número K , la tarea es encontrar los números totales de 0 a N que tienen exactamente K dígitos distintos de cero y la suma de esos dígitos debe ser impar y esa suma debe ser distinta. El número N puede ser tan grande como 10^18 .
Ejemplos: 
 

Entrada: N = 10, K = 1 
Salida: 5 
Los números que siguen las condiciones son -> 
1, 3, 5, 7 y 9 
La suma de dígitos de 10 que es (1+0) = 1 también es impar, pero 1 ya está incluido en nuestro conteo.
Entrada: N = 100, K = 2 
Salida: 8
 

Requisitos previos : Enfoque ingenuo de Digit-DP
: 
un enfoque ingenuo para el recorrido lineal en O (N) de todos los elementos de 0 a N y calcular la suma de dígitos en log (n) donde n es el número de dígitos en ese número fallará para grandes Entradas de N.
Enfoque Eficiente: 
 

1. Podemos usar Programación Dinámica y su técnica muy útil es digit-dp para resolver este problema. 
    
2. Entonces, en lugar de mantener un registro de enteros distintos de cero, mantenemos un registro de ceros que podemos mantener en diferentes índices, idx en la variable K. La cantidad de ceros que podemos mantener se puede encontrar inicialmente restando K con la cantidad de dígitos en NORTE. 
    
3. Mantenemos todos los dígitos de N en un vector, digamos, dígitos . 
    
4. Ahora, calculamos el rango de elementos que podemos mantener en el índice idx analizando K. 
   • Supongamos que en el índice idx , nos quedamos con K = 1 (un valor distinto de cero), entonces nuestro rango para colocar elementos es [0, j] donde j es el límite superior decidido por el valor ajustado obtenido del índice actual del dígito a partir de dígitos vectoriales. 
      
   • Si en idx , nos quedamos con K = 0 , entonces nuestro rango se convierte en [1, j] porque no podemos poner 0 allí. 
      
5. Ahora, también tome un parámetro que sea sum , que calculará la suma de los dígitos de un número hasta que el caso base sea exitoso. 
    
6. Además, se usa un mapa booleano que almacenará todas las sumas impares ya calculadas, por lo que da distintas sumas impares. 
    
7. La recurrencia será:
   
   donde j = dígitos[idx] si apretado = 0, si no j = 9 
    
8. Caso base: 
   • Cuando idx = digits.size() , K == 0 y la suma es impar. 
     Marcamos la suma como verdadera y devolvemos 1, de lo contrario devolvemos 0. 
      
   • Si idx > digits.size() entonces devuelve 0. 
      

Así que creamos una tabla DP, digamos DP[idx][K][tight][sum] que almacenará nuestro resultado de la recurrencia anterior y devolverá el conteo al memorizarlo en esta tabla DP.
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ program to Count the numbers having
// exactly K non-zero digits and sum
// of digits are odd and distinct.
#include <bits/stdc++.h>
using namespace std;
 
// To store digits of N
vector<int> digits;
 
// visited map
bool vis[170] = { false };
 
// DP Table
int dp[19][19][2][170];
 
// Push all the digits of N into
// digits vector
void ConvertIntoDigit(int n)
{
    while (n) {
        int dig = n % 10;
        digits.push_back(dig);
        n /= 10;
    }
    reverse(digits.begin(), digits.end());
}
 
// Function returns the count
int solve(int idx, int k,
          int tight, int sum)
{
    // If desired number is formed
    // whose sum is odd
    if (idx == digits.size()
        && k == 0 && sum & 1) {
        // If it is not present in map,
        // mark it as true and return 1
        if (!vis[sum]) {
            vis[sum] = 1;
            return 1;
        }
        // Sum is present in map already
        return 0;
    }
 
    // Desired result not found
    if (idx > digits.size()) {
        return 0;
    }
 
    // If that state is already calculated
    // just return that state value
    if (dp[idx][k][tight][sum]) {
        return dp[idx][k][tight][sum];
    }
 
    // Upper limit
    int j;
    if (tight == 0) {
        j = digits[idx];
    }
    else {
        j = 9;
    }
 
    // To store the count of
    // desired numbers
    int cnt = 0;
 
    // If k is non-zero, i ranges from
    // 0 to j else [1, j]
    for (int i = (k ? 0 : 1);
         i <= j; i++) {
        int newtight = tight;
 
        if (i < j) {
            newtight = 1;
        }
 
        // If current digit is 0, decrement
        // k and recurse sum is not changed
        // as we are just adding 0 that
        // makes no difference
        if (i == 0)
            cnt += solve(idx + 1, k - 1,
                         newtight, sum);
 
        // If i is non zero, then k remains
        // unchanged and value is added to sum
        else
            cnt += solve(idx + 1, k, newtight,
                         sum + i);
    }
 
    // Memoize and return
    return dp[idx][k][tight][sum] = cnt;
}
 
// Driver code
int main()
{
 
    // K is the number of exact non-zero
    // elements to have in number
    int N, k;
    N = 169, k = 2;
 
    // break N into its digits
    ConvertIntoDigit(N);
 
    // We keep record of 0s we need to
    // place in the number
    k = digits.size() - k;
    cout << solve(0, k, 0, 0);
}

// Java program to count the numbers having
// exactly K non-zero digits and sum
// of digits are odd and distinct.
import java.util.*;
 
class GFG{
 
// To store digits of N
static Vector<Integer> digits = new Vector<Integer>();
 
// visited map
static boolean []vis = new boolean[170];
 
// DP Table
static int [][][][]dp = new int[19][19][2][170];
 
// Push all the digits of N into
// digits vector
static void ConvertIntoDigit(int n)
{
    while (n > 0)
    {
        int dig = n % 10;
        digits.add(dig);
        n /= 10;
    }
    Collections.reverse(digits);
}
 
// Function returns the count
static int solve(int idx, int k,
                 int tight, int sum)
{
     
    // If desired number is formed
    // whose sum is odd
    if (idx == digits.size() &&
          k == 0 && sum % 2 == 1)
    {
         
        // If it is not present in map,
        // mark it as true and return 1
        if (!vis[sum])
        {
            vis[sum] = true;
            return 1;
        }
         
        // Sum is present in map already
        return 0;
    }
 
    // Desired result not found
    if (idx > digits.size())
    {
        return 0;
    }
 
    // If that state is already calculated
    // just return that state value
    if (dp[idx][k][tight][sum] > 0)
    {
        return dp[idx][k][tight][sum];
    }
 
    // Upper limit
    int j;
    if (idx < digits.size() && tight == 0)
    {
        j = digits.get(idx);
    }
    else
    {
        j = 9;
    }
 
    // To store the count of
    // desired numbers
    int cnt = 0;
 
    // If k is non-zero, i ranges from
    // 0 to j else [1, j]
    for(int i = (k > 0 ? 0 : 1); i <= j; i++)
    {
        int newtight = tight;
 
        if (i < j)
        {
            newtight = 1;
        }
 
        // If current digit is 0, decrement
        // k and recurse sum is not changed
        // as we are just adding 0 that
        // makes no difference
        if (i == 0)
            cnt += solve(idx + 1, k - 1,
                         newtight, sum);
 
        // If i is non zero, then k remains
        // unchanged and value is added to sum
        else
            cnt += solve(idx + 1, k, newtight,
                         sum + i);
    }
 
    // Memoize and return
    return dp[idx][k][tight][sum] = cnt;
}
 
// Driver code
public static void main(String[] args)
{
 
    // K is the number of exact non-zero
    // elements to have in number
    int N, k;
    N = 169; k = 2;
 
    // break N into its digits
    ConvertIntoDigit(N);
 
    // We keep record of 0s we need to
    // place in the number
    k = digits.size() - k;
     
    System.out.print(solve(0, k, 0, 0));
}
}
 
// This code is contributed by amal kumar choubey

# Python3 program to Count the numbers having
# exactly K non-zero digits and sum
# of digits are odd and distinct.
  
# To store digits of N
digits = []
  
# visited map
vis = [False for i in range(170)]
  
# DP Table
dp = [[[[0 for l in range(170)] for k in range(2)] for j in range(19)] for i in range(19)]
  
# Push all the digits of N into
# digits vector
def ConvertIntoDigit(n):
 
    while (n > 0):
        dig = n % 10;
        digits.append(dig);
        n //= 10;
    digits.reverse()
     
# Function returns the count
def solve(idx, k, tight, sum):
 
    # If desired number is formed
    # whose sum is odd
    if (idx == len(digits) and k == 0 and sum % 2 == 1):
         
        # If it is not present in map,
        # mark it as true and return 1
        if (not vis[sum]):
            vis[sum] = True;
            return 1;
         
        # Sum is present in map already
        return 0;
     
    # Desired result not found
    if (idx > len(digits)):
        return 0;
     
    # If that state is already calculated
    # just return that state value
    if (dp[idx][k][tight][sum]):
        return dp[idx][k][tight][sum];
     
    # Upper limit
    j = 0;
    if (idx<len(digits) and tight == 0):
        j = digits[idx];
     
    else:
        j = 9;
     
    # To store the count of
    # desired numbers
    cnt = 0;
  
    # If k is non-zero, i ranges from
    # 0 to j else [1, j]
    for i in range(0 if k else 1, j + 1):
        newtight = tight;
  
        if (i < j):
            newtight = 1;
  
        # If current digit is 0, decrement
        # k and recurse sum is not changed
        # as we are just adding 0 that
        # makes no difference
        if (i == 0):
            cnt += solve(idx + 1, k - 1, newtight, sum);
  
        # If i is non zero, then k remains
        # unchanged and value is added to sum
        else:  
            cnt += solve(idx + 1, k, newtight, sum + i);
     
    dp[idx][k][tight][sum] = cnt
     
    # Memoize and return
    return cnt;
 
# Driver code
if __name__=='__main__':
  
    # K is the number of exact non-zero
    # elements to have in number
    N = 169
    k = 2;
  
    # break N into its digits
    ConvertIntoDigit(N);
  
    # We keep record of 0s we need to
    # place in the number
    k = len(digits) - k;
    print(solve(0, k, 0, 0))
 
# This code is contributed by rutvik_56.

// C# program to count the numbers having
// exactly K non-zero digits and sum
// of digits are odd and distinct.
using System;
using System.Collections.Generic;
 
class GFG{
 
// To store digits of N
static List<int> digits = new List<int>();
 
// visited map
static bool []vis = new bool[170];
 
// DP Table
static int [,,,]dp = new int[ 19, 19, 2, 170 ];
 
// Push all the digits of N into
// digits vector
static void ConvertIntoDigit(int n)
{
    while (n > 0)
    {
        int dig = n % 10;
        digits.Add(dig);
        n /= 10;
    }
    digits.Reverse();
}
 
// Function returns the count
static int solve(int idx, int k,
                 int tight, int sum)
{
     
    // If desired number is formed
    // whose sum is odd
    if (idx == digits.Count &&
          k == 0 && sum % 2 == 1)
    {
         
        // If it is not present in map,
        // mark it as true and return 1
        if (!vis[sum])
        {
            vis[sum] = true;
            return 1;
        }
         
        // Sum is present in map already
        return 0;
    }
 
    // Desired result not found
    if (idx > digits.Count)
    {
        return 0;
    }
 
    // If that state is already calculated
    // just return that state value
    if (dp[idx, k, tight, sum] > 0)
    {
        return dp[idx, k, tight, sum];
    }
 
    // Upper limit
    int j;
    if (idx < digits.Count && tight == 0)
    {
        j = digits[idx];
    }
    else
    {
        j = 9;
    }
 
    // To store the count of
    // desired numbers
    int cnt = 0;
 
    // If k is non-zero, i ranges from
    // 0 to j else [1, j]
    for(int i = (k > 0 ? 0 : 1); i <= j; i++)
    {
        int newtight = tight;
 
        if (i < j)
        {
            newtight = 1;
        }
 
        // If current digit is 0, decrement
        // k and recurse sum is not changed
        // as we are just adding 0 that
        // makes no difference
        if (i == 0)
            cnt += solve(idx + 1, k - 1,
                         newtight, sum);
 
        // If i is non zero, then k remains
        // unchanged and value is added to sum
        else
            cnt += solve(idx + 1, k, newtight,
                         sum + i);
    }
 
    // Memoize and return
    return dp[idx, k, tight, sum] = cnt;
}
 
// Driver code
public static void Main(String[] args)
{
     
    // K is the number of exact non-zero
    // elements to have in number
    int N, k;
    N = 169; k = 2;
 
    // break N into its digits
    ConvertIntoDigit(N);
 
    // We keep record of 0s we need to
    // place in the number
    k = digits.Count - k;
     
    Console.Write(solve(0, k, 0, 0));
}
}
 
// This code is contributed by amal kumar choubey

<script>
 
    // JavaScript program to count the numbers having
    // exactly K non-zero digits and sum
    // of digits are odd and distinct.
     
    // To store digits of N
    let digits = [];
 
    // visited map
    let vis = new Array(170);
    vis.fill(false);
 
    // DP Table
    let dp = new Array(19);
    for(let i = 0; i < 19; i++)
    {
        dp[i] = new Array(19);
        for(let j = 0; j < 19; j++)
        {
            dp[i][j] = new Array(2);
            for(let k = 0; k < 2; k++)
            {
                dp[i][j][k] = new Array(170);
                for(let l = 0; l < 170; l++)
                {
                    dp[i][j][k][l] = 0;
                }
            }
        }
    }
 
    // Push all the digits of N into
    // digits vector
    function ConvertIntoDigit(n)
    {
        while (n > 0)
        {
            let dig = n % 10;
            digits.push(dig);
            n = parseInt(n / 10, 10);
        }
        digits.reverse();
    }
 
    // Function returns the count
    function solve(idx, k, tight, sum)
    {
 
        // If desired number is formed
        // whose sum is odd
        if (idx == digits.length &&
              k == 0 && sum % 2 == 1)
        {
 
            // If it is not present in map,
            // mark it as true and return 1
            if (!vis[sum])
            {
                vis[sum] = true;
                return 1;
            }
 
            // Sum is present in map already
            return 0;
        }
 
        // Desired result not found
        if (idx > digits.length)
        {
            return 0;
        }
 
        // If that state is already calculated
        // just return that state value
        if (dp[idx][k][tight][sum] > 0)
        {
            return dp[idx][k][tight][sum];
        }
 
        // Upper limit
        let j;
        if (idx < digits.length && tight == 0)
        {
            j = digits[idx];
        }
        else
        {
            j = 9;
        }
 
        // To store the count of
        // desired numbers
        let cnt = 0;
 
        // If k is non-zero, i ranges from
        // 0 to j else [1, j]
        for(let i = (k > 0 ? 0 : 1); i <= j; i++)
        {
            let newtight = tight;
 
            if (i < j)
            {
                newtight = 1;
            }
 
            // If current digit is 0, decrement
            // k and recurse sum is not changed
            // as we are just adding 0 that
            // makes no difference
            if (i == 0)
                cnt += solve(idx + 1, k - 1,
                             newtight, sum);
 
            // If i is non zero, then k remains
            // unchanged and value is added to sum
            else
                cnt += solve(idx + 1, k, newtight,
                             sum + i);
        }
 
        // Memoize and return
        dp[idx][k][tight][sum] = cnt;
        return dp[idx][k][tight][sum];
    }
     
    // K is the number of exact non-zero
    // elements to have in number
    let N, k;
    N = 169; k = 2;
  
    // break N into its digits
    ConvertIntoDigit(N);
  
    // We keep record of 0s we need to
    // place in the number
    k = digits.length - k;
      
    document.write(solve(0, k, 0, 0));
 
</script>

12