Number of integers of size N having even sum of digits
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 109 + 7. (1 <= N <= 105)
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(10N)
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 initiallized 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; }
Time Complexity: O(N)
Auxiliary Space: O(N)
Related Articles:
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 109 + 7. (1 <= N <= 105)
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(10N)
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 initiallized 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; }
Time Complexity: O(N)
Auxiliary Space: O(N)
Related Articles: