Count numbers with exactly K non-zero digits and distinct odd digit sum

0 0 11 minutes read

Given an Integer N, and a number K, the task is to find out the total numbers from 0 to N which have exactly K non zero digits and the sum of those digits should be odd and that sum should be distinct. The number N can be as large as 10^18.
Examples:

Input : N = 10, K = 1
Output : 5
The numbers which follow the conditions are ->
1, 3, 5, 7 and 9
The digit sum of 10 that is (1+0) = 1 is also odd, but 1 is already included in our count.
Input : N = 100, K = 2
Output : 8

Prerequisites: Digit-DP
Naive Approach:
A naive approach for linear traversing in O(N) of all elements from 0 to N and calculating sum of digits in log(n) where n is the number of digits in that number will fail for large inputs of N.
Efficient Approach:

We can use Dynamic Programming and it’s very useful technique that is digit-dp to solve this problem.
So instead of keeping a record of non-zero integers, we keep a record of zeroes we can keep at different indices, idx in variable K. The number of zeroes we can keep can be found initially by subtracting K with the number of digits in N.
We keep all the digits of N into a vector say, digits.
Now, we calculate range of elements we can keep at index idx by analysing K.
- Suppose at index idx, we are left with K = 1 (A Non-zero value), then our range to put elements is [0, j] where j is the upper bound decided by the tight value obtained from the current index of the digit from vector digits.
- If at idx, we are left with K = 0, then our range becomes [1, j] because we can’t put in 0 there.
Now, also take a parameter that is sum, which will calculate the sum of digits of a number till the base case hits successfully.
Also, a boolean map is used which will store all the odd sums calculated already, so it gives distinct odd sums.
The recurrence will be:
$f(idx, K, tight, sum) = $\sum_{i=0}^{j} f(idx+1, K-1, newtight, sum+i) f(idx, K, tight, sum) = $\sum_{i=1}^{j} f(idx+1, K, newtight, sum+i)$
where j = digits[idx] if tight = 0, else j = 9
Base Case:
- When idx = digits.size(), K == 0 and sum is odd.
  We mark the sum as true and return 1 else return 0.
- If idx > digits.size() then return 0.

So we create a DP table say DP[idx][K][tight][sum] which will store our result from the recurrence above and return the count by memoizing it to this DP table.
Below is the implementation of the above approach:

C++

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

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

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

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

Javascript

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

Output:

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!