Number of integers of size N having even sum of digits

0 0 10 minutes read

Given the number N, the task is to count a number of ways to create a number with digit size N with the sum of digits even. print the answer modulo 10⁹ + 7. (1 <= N <= 10⁵)

Examples:

Input: N = 1
Output: 4
Explanation: 2, 4, 6 and 8 are the numbers.

Input: N = 2
Output: 45
Explanation: 11, 13, 15, 17, 19, 20, 22, 24, 26, 28, 31, 33, 35, 37, 39, 40, 42, 44, 46, 48, 51, 53, 55, 57, 59, 60, 62, 64, 66, 68, 71, 73, 75, 77, 79, 80, 82, 84, 86, 88, 91, 93, 95, 97, and 99 are the possible numbers.

Naive approach: The basic way to solve the problem is as follows:

The basic way to solve this problem is to generate all possible combinations by using a recursive approach.

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

Efficient Approach: The above approach can be optimized based on the following idea:

Dynamic programming can be used to solve this problem. For solving this problem its very simple to make finite automata machine for states with following transitions:

dp[i][j] represents number of ways of creating numbers with i digits and j represents current state of state machine.

It can be observed that the recursive function is called exponential times. That means that some states are called repeatedly.

So the idea is to store the value of each state. This can be done by using the stored value of a state and whenever the function is called, return the stored value without computing again.

Follow the steps below to solve the problem:

Create a recursive function that takes two parameters representing i’th position to be filled with digit and j representing the current state of Finite State Machine.
Call the recursive function for choosing all digits from 0 to 9.
Base case if digit of size N formed return 1 if the current state even else returns 0.
Create a 2d array of dp[N][3] initially filled with -1.
If the answer for a particular state is computed then save it in dp[i][j].
If the answer for a particular state is already computed then just return dp[i][j].

Below is the implementation of the above approach:

C++

// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
 
const int MOD = 1e9 + 7;
 
// DP table initialized with -1
int dp[1000001][3];
 
// Recursive Function to count ways to create
// number of N digits such that its digit sum
// is even.
int recur(int i, int j)
{
    // Base case
    if (i == 0) {
 
        // If current sum is even
        if (j == 2)
            return 1;
 
        // Else if sum is odd
        else
            return 0;
    }
 
    // If answer for current state is already
    // calculated then just return dp[i][j]
    if (dp[i][j] != -1)
        return dp[i][j];
 
    // Answer initialized with zero
    int ans = 0;
 
    // start state of automata machine
    if (j == 0) {
        // If odd digit is picked then it
        // will move to automata state 1
        for (int k = 1; k <= 9; k += 2) {
            ans += recur(i - 1, 1);
            ans %= MOD;
        }
 
        // If even digit is picked then it
        // will move to automata state 2
        for (int k = 2; k <= 8; k += 2) {
            ans += recur(i - 1, 2);
            ans %= MOD;
        }
    }
 
    // Odd state of automata machine
    else if (j == 1) {
 
        // If odd digit picked then it
        // will move to automata state 2
        for (int k = 1; k <= 9; k += 2) {
            ans += recur(i - 1, 2);
            ans %= MOD;
        }
 
        // If even digit picked then it
        // will remain on same state 1
        for (int k = 2; k <= 8; k += 2) {
            ans += recur(i - 1, 1);
            ans %= MOD;
        }
    }
 
    // Even state of automata machine
    else {
 
        // If odd digit picked then it
        // will move to state 1
        for (int k = 1; k <= 9; k += 2) {
            ans += recur(i - 1, 1);
            ans %= MOD;
        }
 
        // If even digit picked then it
        // will remain on current state 2.
        for (int k = 0; k <= 8; k += 2) {
 
            ans += recur(i - 1, 2);
            ans %= MOD;
        }
    }
 
    // Save and return dp value
    return dp[i][j] = ans;
}
 
// Function to count ways to create
// number of N digits such that its digit
// sum is even.
int countWaysTo(int N)
{
 
    // Initializing dp array with - 1
    memset(dp, -1, sizeof(dp));
 
    return recur(N, 0);
}
 
// Driver Code
int main()
{
    // Input 1
    int N = 1;
 
    // Function Call
    cout << countWaysTo(N) << endl;
 
    // Input 2
    int N1 = 2;
 
    // Function Call
    cout << countWaysTo(N1) << endl;
    return 0;
}

Java

// Java code to implement the approach
 
import java.io.*;
import java.util.*;
 
class GFG {
 
static int MOD = 1000000000 + 7;
 
// DP table initialized with -1
static int dp[][] = new int[1000001][3];
 
// Recursive Function to count ways to create
// number of N digits such that its digit sum
// is even.
static int recur(int i, int j)
{
    // Base case
    if (i == 0) {
 
        // If current sum is even
        if (j == 2)
            return 1;
 
        // Else if sum is odd
        else
            return 0;
    }
 
    // If answer for current state is already
    // calculated then just return dp[i][j]
    if (dp[i][j] != -1)
        return dp[i][j];
 
    // Answer initialized with zero
    int ans = 0;
 
    // start state of automata machine
    if (j == 0) {
        // If odd digit is picked then it
        // will move to automata state 1
        for (int k = 1; k <= 9; k += 2) {
            ans += recur(i - 1, 1);
            ans %= MOD;
        }
 
        // If even digit is picked then it
        // will move to automata state 2
        for (int k = 2; k <= 8; k += 2) {
            ans += recur(i - 1, 2);
            ans %= MOD;
        }
    }
 
    // Odd state of automata machine
    else if (j == 1) {
 
        // If odd digit picked then it
        // will move to automata state 2
        for (int k = 1; k <= 9; k += 2) {
            ans += recur(i - 1, 2);
            ans %= MOD;
        }
 
        // If even digit picked then it
        // will remain on same state 1
        for (int k = 2; k <= 8; k += 2) {
            ans += recur(i - 1, 1);
            ans %= MOD;
        }
    }
 
    // Even state of automata machine
    else {
 
        // If odd digit picked then it
        // will move to state 1
        for (int k = 1; k <= 9; k += 2) {
            ans += recur(i - 1, 1);
            ans %= MOD;
        }
 
        // If even digit picked then it
        // will remain on current state 2.
        for (int k = 0; k <= 8; k += 2) {
 
            ans += recur(i - 1, 2);
            ans %= MOD;
        }
    }
 
    // Save and return dp value
    return dp[i][j] = ans;
}
 
// Function to count ways to create
// number of N digits such that its digit
// sum is even.
static int countWaysTo(int N)
{
 
    // Initializing dp array with - 1
    for(int i=0;i<1000001;i++)
    {
        for(int j=0;j<3;j++)
        {
            dp[i][j]=-1;
        }
    }
 
    return recur(N, 0);
}
 
     
// Driver code
public static void main(String[] args)
{
    // Input 1
    int N = 1;
 
    // Function Call
    System.out.println(countWaysTo(N));
 
    // Input 2
    int N1 = 2;
 
    // Function Call
    System.out.println(countWaysTo(N1));
}
}

Python3

MOD = int(1e9 + 7)
 
# DP table initialized with -1
dp = [[-1 for _ in range(3)] for _ in range(1000001)]
 
# Recursive Function to count ways to create
# number of N digits such that its digit sum
# is even.
def recur(i: int, j: int) -> int:
    # Base case
    if i == 0:
        # If current sum is even
        if j == 2:
            return 1
        # Else if sum is odd
        else:
            return 0
    # If answer for current state is already
    # calculated then just return dp[i][j]
    if dp[i][j] != -1:
        return dp[i][j]
    # Answer initialized with zero
    ans = 0
    # start state of automata machine
    if j == 0:
        # If odd digit is picked then it
        # will move to automata state 1
        for k in range(1, 10, 2):
            ans += recur(i-1, 1)
            ans %= MOD
        # If even digit is picked then it
        # will move to automata state 2
        for k in range(2, 9, 2):
            ans += recur(i-1, 2)
            ans %= MOD
    # Odd state of automata machine
    elif j == 1:
        # If odd digit picked then it
        # will move to automata state 2
        for k in range(1, 10, 2):
            ans += recur(i-1, 2)
            ans %= MOD
        # If even digit picked then it
        # will remain on same state 1
        for k in range(2, 9, 2):
            ans += recur(i-1, 1)
            ans %= MOD
    # Even state of automata machine
    else:
        # If odd digit picked then it
        # will move to state 1
        for k in range(1, 10, 2):
            ans += recur(i-1, 1)
            ans %= MOD
        # If even digit picked then it
        # will remain on current state 2.
        for k in range(0, 9, 2):
            ans += recur(i-1, 2)
            ans %= MOD
    # Save and return dp value
    dp[i][j] = ans
    return ans
 
# Function to count ways to create
# number of N digits such that its digit
# sum is even.
def countWaysTo(N: int) -> int:
    return recur(N, 0)
 
# Driver Code
if __name__ == "__main__":
    # Input 1
    N = 1
    # Function Call
    print(countWaysTo(N))
    # Input 2
    N1 = 2
    # Function Call
    print(countWaysTo(N1))

C#

// C# code to implement the approach
 
using System;
using System.Collections.Generic;
 
class GFG {
     
    static int MOD = 1000000007;
 
    // DP table initialized with -1
    static int[,] dp=new int[1000001,3];
     
    // Recursive Function to count ways to create
    // number of N digits such that its digit sum
    // is even.
    static int recur(int i, int j)
    {
        // Base case
        if (i == 0) {
     
            // If current sum is even
            if (j == 2)
                return 1;
     
            // Else if sum is odd
            else
                return 0;
        }
     
        // If answer for current state is already
        // calculated then just return dp[i][j]
        if (dp[i,j] != -1)
            return dp[i,j];
     
        // Answer initialized with zero
        int ans = 0;
     
        // start state of automata machine
        if (j == 0) {
            // If odd digit is picked then it
            // will move to automata state 1
            for (int k = 1; k <= 9; k += 2) {
                ans += recur(i - 1, 1);
                ans %= MOD;
            }
     
            // If even digit is picked then it
            // will move to automata state 2
            for (int k = 2; k <= 8; k += 2) {
                ans += recur(i - 1, 2);
                ans %= MOD;
            }
        }
     
        // Odd state of automata machine
        else if (j == 1) {
     
            // If odd digit picked then it
            // will move to automata state 2
            for (int k = 1; k <= 9; k += 2) {
                ans += recur(i - 1, 2);
                ans %= MOD;
            }
     
            // If even digit picked then it
            // will remain on same state 1
            for (int k = 2; k <= 8; k += 2) {
                ans += recur(i - 1, 1);
                ans %= MOD;
            }
        }
     
        // Even state of automata machine
        else {
     
            // If odd digit picked then it
            // will move to state 1
            for (int k = 1; k <= 9; k += 2) {
                ans += recur(i - 1, 1);
                ans %= MOD;
            }
     
            // If even digit picked then it
            // will remain on current state 2.
            for (int k = 0; k <= 8; k += 2) {
     
                ans += recur(i - 1, 2);
                ans %= MOD;
            }
        }
     
        // Save and return dp value
        return dp[i,j] = ans;
    }
     
    // Function to count ways to create
    // number of N digits such that its digit
    // sum is even.
    static int countWaysTo(int N)
    {
     
        // Initializing dp array with - 1
        for(int i=0; i<1000001; i++)
        {
            for(int j=0;j<3; j++)
                dp[i,j]=-1;
        }
        return recur(N, 0);
    }
     
    // Driver Code
    public static void Main()
    {
        // Input 1
        int N = 1;
     
        // Function Call
        Console.Write(countWaysTo(N)+"\n");
     
        // Input 2
        int N1 = 2;
     
        // Function Call
        Console.Write(countWaysTo(N1)+"\n");
    }
}

Javascript

// Javascript code to implement the approach
 
const  MOD = 1e9 + 7;
 
// DP table initialized with -1
let dp=new Array(1000001)
for(let i=0; i<1000001; i++)
    dp[i]=new Array(3).fill(-1);
 
// Recursive Function to count ways to create
// number of N digits such that its digit sum
// is even.
function recur( i, j)
{
    // Base case
    if (i == 0) {
 
        // If current sum is even
        if (j == 2)
            return 1;
 
        // Else if sum is odd
        else
            return 0;
    }
 
    // If answer for current state is already
    // calculated then just return dp[i][j]
    if (dp[i][j] != -1)
        return dp[i][j];
 
    // Answer initialized with zero
    let ans = 0;
 
    // start state of automata machine
    if (j == 0) {
        // If odd digit is picked then it
        // will move to automata state 1
        for (let k = 1; k <= 9; k += 2) {
            ans += recur(i - 1, 1);
            ans %= MOD;
        }
 
        // If even digit is picked then it
        // will move to automata state 2
        for (let k = 2; k <= 8; k += 2) {
            ans += recur(i - 1, 2);
            ans %= MOD;
        }
    }
 
    // Odd state of automata machine
    else if (j == 1) {
 
        // If odd digit picked then it
        // will move to automata state 2
        for (let k = 1; k <= 9; k += 2) {
            ans += recur(i - 1, 2);
            ans %= MOD;
        }
 
        // If even digit picked then it
        // will remain on same state 1
        for (let k = 2; k <= 8; k += 2) {
            ans += recur(i - 1, 1);
            ans %= MOD;
        }
    }
 
    // Even state of automata machine
    else {
 
        // If odd digit picked then it
        // will move to state 1
        for (let k = 1; k <= 9; k += 2) {
            ans += recur(i - 1, 1);
            ans %= MOD;
        }
 
        // If even digit picked then it
        // will remain on current state 2.
        for (let k = 0; k <= 8; k += 2) {
 
            ans += recur(i - 1, 2);
            ans %= MOD;
        }
    }
 
    // Save and return dp value
    return dp[i][j] = ans;
}
 
// Function to count ways to create
// number of N digits such that its digit
// sum is even.
function countWaysTo( N)
{
    return recur(N, 0);
}
 
// Driver Code
// Input 1
let N = 1;
 
// Function Call
console.log(countWaysTo(N));
 
// Input 2
let N1 = 2;
 
// Function Call
console.log(countWaysTo(N1));

Output

4
45

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

Related Articles:

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!