Given a positive integer N, the task is to count the number of N-digit numbers whose sum of digits is a prime number.
Examples:
Input: N = 1
Output: 4
Explanation: [2, 3, 5, 7] are single digit numbers whose sum of digits is equal to a prime number.Input : N = 2
Output : 33
Naive Approach: The simplest approach to solve the given problem is to generate all possible N-digit numbers and count those numbers whose sum of digits is a prime number. After checking for all the numbers, print the value of the count as the resultant total count of numbers.
Time Complexity: O(N *10N)
Efficient Approach: The above approach can also be optimized by using Recursive Dynamic Programming because the above problem has overlapping subproblems and an optimal substructure. Follow the steps below to solve the problem:
- Initialize a global 2D array dp[N+1][N*10] with all values as -1 that stores the result of each recursive call.
- Compute prime numbers upto (N * 10) numbers by using Sieve of Eratosthenes.
- Define a recursive function, say countOfNumbers(index, sum, N) by performing the following steps.
- If the value of the index is N+1,
- If the sum is a prime number, return 1 as a valid N-digit number has been formed.
- Else return 0.
- If the result of the state dp[index][sum] is already computed, return this value dp[index][sum].
- If the current index is 1, then any digit from [1- 9] can be placed, else, [0-9] can be placed.
- After making a valid placement of digits, recursively call the countOfNumbers function for the next index, and sum up all recursive pending results into variable val.
- Store the value of val into the current state of the dp[index][sum] table.
- Return this state’s result val to it’s parent recursive call.
- If the value of the index is N+1,
- Print the value returned by the function countOfNumbers(1, 0, N) as the result.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>using namespace std;// Stores the dp statesint dp[100][1000];// Check if a number is// a prime or notbool prime[1005];// Function to generate all prime numbers// that are less than or equal to nvoid SieveOfEratosthenes(int n){ // Base cases. prime[0] = prime[1] = false; for (int p = 2; p * p <= n; p++) { // If prime[p] is not changed, // then it is a prime if (prime[p] == true) { // Update all multiples // of as non-prime for (int i = p * p; i <= n; i += p) prime[i] = false; } }}// Function to find the count of N-digit numbers// such that the sum of digits is a prime numberint countOfNumbers(int index, int sum, int N){ // If end of array is reached if (index == N + 1) { // If the sum is equal to a prime number if (prime[sum] == true) { return 1; } // Otherwise return 0; } int& val = dp[index][sum]; // If the dp-states are already computed if (val != -1) { return val; } val = 0; // If index = 1, any digit from [1 - 9] can be placed. // If N = 1, 0 also can be placed. if (index == 1) { for (int digit = (N == 1 ? 0 : 1); digit <= 9; ++digit) { val += countOfNumbers(index + 1, sum + digit, N); } } // Otherwise, any digit from [0 - 9] can be placed. else { for (int digit = 0; digit <= 9; ++digit) { val += countOfNumbers(index + 1, sum + digit, N); } } // Return the answer. return val;}// Driver Codeint main(){ // Initializing dp array with -1 memset(dp, -1, sizeof dp); // Initializing prime array to true memset(prime, true, sizeof(prime)); // Find all primes less than or equal to 1000, // which is sufficient for N upto 100 SieveOfEratosthenes(1000); // Given Input int N = 6; // Function call cout << countOfNumbers(1, 0, N); return 0;} |
Java
import java.util.Arrays;class GFG{// Stores the dp statespublic static int[][] dp = new int[100][1000];// Check if a number is// a prime or notpublic static boolean[] prime = new boolean[1005];// Function to generate all prime numbers// that are less than or equal to npublic static void SieveOfEratosthenes(int n){ // Base cases. prime[0] = prime[1] = false; for(int p = 2; p * p <= n; p++) { // If prime[p] is not changed, // then it is a prime if (prime[p] == true) { // Update all multiples // of as non-prime for(int i = p * p; i <= n; i += p) prime[i] = false; } }}// Function to find the count of N-digit numbers// such that the sum of digits is a prime numberpublic static int countOfNumbers(int index, int sum, int N){ // If end of array is reached if (index == N + 1) { // If the sum is equal to a prime number if (prime[sum] == true) { return 1; } // Otherwise return 0; } int val = dp[index][sum]; // If the dp-states are already computed if (val != -1) { return val; } val = 0; // If index = 1, any digit from [1 - 9] can be placed. // If N = 1, 0 also can be placed. if (index == 1) { for(int digit = (N == 1 ? 0 : 1); digit <= 9; ++digit) { val += countOfNumbers(index + 1, sum + digit, N); } } // Otherwise, any digit from [0 - 9] can be placed. else { for(int digit = 0; digit <= 9; ++digit) { val += countOfNumbers(index + 1, sum + digit, N); } } // Return the answer. return val;}// Driver Codepublic static void main(String args[]){ // Initializing dp array with -1 for(int[] row : dp) Arrays.fill(row, -1); // Initializing prime array to true Arrays.fill(prime, true); // Find all primes less than or equal to 1000, // which is sufficient for N upto 100 SieveOfEratosthenes(1000); // Given Input int N = 6; // Function call System.out.println(countOfNumbers(1, 0, N));}}// This code is contributed by gfgking |
Python3
# Python program for the above approach# Stores the dp statesdp = [[-1]*100]*1000# Check if a number is# a prime or notprime = [True] * 1005# Function to generate all prime numbers# that are less than or equal to ndef SieveOfEratosthenes(n) : # Base cases. prime[0] = prime[1] = False p = 2 while(p * p <= n): # If prime[p] is not changed, # then it is a prime if (prime[p] == True) : # Update all multiples # of as non-prime for i in range(p * p, n+1, p) : prime[i] = False p += 1# Function to find the count of N-digit numbers# such that the sum of digits is a prime numberdef countOfNumbers(index, sum, N) : # If end of array is reached if (index == N + 1) : # If the sum is equal to a prime number if (prime[sum] == True) : return 1 # Otherwise return 0 val = dp[index][sum] # If the dp-states are already computed if (val != -1) : return val val = 0 # If index = 1, any digit from [1 - 9] can be placed. # If N = 1, 0 also can be placed. if (index == 1) : for digit in range(((0, 1) [N == 1])+1, 10, 1) : val += countOfNumbers(index + 1, sum + digit, N) # Otherwise, any digit from [0 - 9] can be placed. else : for digit in range(0, 10, 1) : val += countOfNumbers(index + 1, sum + digit, N) # Return the answer. return val# Driver Code# Find all primes less than or equal to 1000,# which is sufficient for N upto 100SieveOfEratosthenes(1000)# Given InputN = 6# Function callprint(countOfNumbers(1, 0, N))# This code is contributed by avijitmondal1998. |
C#
using System;public class GFG{// Stores the dp statespublic static int[,] dp = new int[100,1000];// Check if a number is// a prime or notpublic static bool[] prime = new bool[1005];// Function to generate all prime numbers// that are less than or equal to npublic static void SieveOfEratosthenes(int n){ // Base cases. prime[0] = prime[1] = false; for(int p = 2; p * p <= n; p++) { // If prime[p] is not changed, // then it is a prime if (prime[p] == true) { // Update all multiples // of as non-prime for(int i = p * p; i <= n; i += p) prime[i] = false; } }}// Function to find the count of N-digit numbers// such that the sum of digits is a prime numberpublic static int countOfNumbers(int index, int sum, int N){ // If end of array is reached if (index == N + 1) { // If the sum is equal to a prime number if (prime[sum] == true) { return 1; } // Otherwise return 0; } int val = dp[index,sum]; // If the dp-states are already computed if (val != -1) { return val; } val = 0; // If index = 1, any digit from [1 - 9] can be placed. // If N = 1, 0 also can be placed. if (index == 1) { for(int digit = (N == 1 ? 0 : 1); digit <= 9; ++digit) { val += countOfNumbers(index + 1, sum + digit, N); } } // Otherwise, any digit from [0 - 9] can be placed. else { for(int digit = 0; digit <= 9; ++digit) { val += countOfNumbers(index + 1, sum + digit, N); } } // Return the answer. return val;}// Driver Codepublic static void Main(String []args){ // Initializing dp array with -1 for(int i = 0; i < 100; i++) { for (int j = 0; j < 1000; j++) { dp[i,j] = -1; } } // Initializing prime array to true for (int i = 0; i < prime.Length; i++) prime[i] = true; // Find all primes less than or equal to 1000, // which is sufficient for N upto 100 SieveOfEratosthenes(1000); // Given Input int N = 6; // Function call Console.WriteLine(countOfNumbers(1, 0, N));}}// This code is contributed by Princi Singh |
Javascript
<script>// Stores the dp stateslet dp = new Array(100).fill(0).map(() => new Array(1000).fill(-1));// Check if a number is// a prime or notlet prime = new Array(1005).fill(true);// Function to generate all prime numbers// that are less than or equal to nfunction SieveOfEratosthenes(n) { // Base cases. prime[0] = prime[1] = false; for(let p = 2; p * p <= n; p++) { // If prime[p] is not changed, // then it is a prime if (prime[p] == true) { // Update all multiples // of as non-prime for(let i = p * p; i <= n; i += p) prime[i] = false; } }}// Function to find the count of N-digit numbers// such that the sum of digits is a prime numberfunction countOfNumbers(index, sum, N){ // If end of array is reached if (index == N + 1) { // If the sum is equal to a prime number if (prime[sum] == true) { return 1; } // Otherwise return 0; } let val = dp[index][sum]; // If the dp-states are already computed if (val != -1) { return val; } val = 0; // If index = 1, any digit from [1 - 9] can // be placed. If N = 1, 0 also can be placed. if (index == 1) { for(let digit = N == 1 ? 0 : 1; digit <= 9; ++digit) { val += countOfNumbers(index + 1, sum + digit, N); } } // Otherwise, any digit from [0 - 9] // can be placed. else { for(let digit = 0; digit <= 9; ++digit) { val += countOfNumbers(index + 1, sum + digit, N); } } // Return the answer. return val;}// Driver Code// Find all primes less than or equal to 1000,// which is sufficient for N upto 100SieveOfEratosthenes(1000);// Given Inputlet N = 6;// Function calldocument.write(countOfNumbers(1, 0, N));// This code is contributed by gfgking</script> |
Output:
222638
Time Complexity: O(N2 * 10)
Auxiliary Space: O(N2)
Efficient approach : Using DP Tabulation method ( Iterative approach )
The approach to solve this problem is same but DP tabulation(bottom-up) method is better then Dp + memoization(top-down) because memoization method needs extra stack space of recursion calls.
Steps to solve this problem :
- Create a DP to store the solution of the subproblems and initialize it with 0.
- Initialize the DP with base cases.
- Now Iterate over subproblems to get the value of current problem form previous computation of subproblems stored in DP.
- Create a variable ans to store the final result and iterate over DP to update ans.
- At last return and print the final solution stored in ans.
Implementation :
C++
// C++ code for above approach#include <bits/stdc++.h>using namespace std;// Function to generate all prime numbers// that are less than or equal to nvoid SieveOfEratosthenes(int n, bool prime[]) { prime[0] = prime[1] = false; for (int p = 2; p * p <= n; p++) { if (prime[p] == true) { for (int i = p * p; i <= n; i += p) prime[i] = false; } }}// Function to find the count of N-digit numbers// such that the sum of digits is a prime numberint countOfNumbers(int N) { // Stores the dp states int dp[N + 1][1000]; // Initializing dp array with 0 memset(dp, 0, sizeof(dp)); // Initializing prime array to true bool prime[1005]; memset(prime, true, sizeof(prime)); // Find all primes less than or equal to 1000, // which is sufficient for N upto 100 SieveOfEratosthenes(1000, prime); // Base cases for (int i = 1; i <= 9; i++) dp[1][i] = 1; if (N == 1) dp[1][0] = 1; // Fill the dp table for (int i = 2; i <= N; i++) { for (int j = 0; j <= 900; j++) { for (int k = 0; k <= 9; k++) { dp[i][j + k] += dp[i - 1][j]; } } } int ans = 0; for (int i = 2; i <= 900; i++) { if (prime[i]) ans += dp[N][i]; } // Return the answer return ans;}// Driver Codeint main() { // Given Input int N = 6; // Function call cout << countOfNumbers(N); return 0;}// this code is contributed by bhardwajji |
Java
import java.util.Arrays;public class Main { // Function to generate all prime numbers // that are less than or equal to n public static void SieveOfEratosthenes(int n, boolean[] prime) { prime[0] = prime[1] = false; for (int p = 2; p * p <= n; p++) { if (prime[p] == true) { for (int i = p * p; i <= n; i += p) prime[i] = false; } } } // Function to find the count of N-digit numbers // such that the sum of digits is a prime number public static int countOfNumbers(int N) { // Stores the dp states int[][] dp = new int[N + 1][1000]; // Initializing dp array with 0 for (int[] row : dp) { Arrays.fill(row, 0); } // Initializing prime array to true boolean[] prime = new boolean[1005]; Arrays.fill(prime, true); // Find all primes less than or equal to 1000, // which is sufficient for N upto 100 SieveOfEratosthenes(1000, prime); // Base cases for (int i = 1; i <= 9; i++) dp[1][i] = 1; if (N == 1) dp[1][0] = 1; // Fill the dp table for (int i = 2; i <= N; i++) { for (int j = 0; j <= 900; j++) { for (int k = 0; k <= 9; k++) { dp[i][j + k] += dp[i - 1][j]; } } } int ans = 0; for (int i = 2; i <= 900; i++) { if (prime[i]) ans += dp[N][i]; } // Return the answer return ans; } // Driver Code public static void main(String[] args) { // Given Input int N = 6; // Function call System.out.println(countOfNumbers(N)); }} |
Python3
import math# Function to generate all prime numbers# that are less than or equal to ndef SieveOfEratosthenes(n): prime = [True] * (n+1) prime[0] = prime[1] = False for p in range(2, int(math.sqrt(n))+1): if prime[p] == True: for i in range(p*p, n+1, p): prime[i] = False return prime# Function to find the count of N-digit numbers# such that the sum of digits is a prime numberdef countOfNumbers(N): # Stores the dp states dp = [[0]*1000 for i in range(N+1)] # Initializing prime array to true prime = [True]*1005 prime = SieveOfEratosthenes(1000) # Base cases for i in range(1, 10): dp[1][i] = 1 if N == 1: dp[1][0] = 1 # Fill the dp table for i in range(2, N+1): for j in range(0, 901): for k in range(0, 10): dp[i][j+k] += dp[i-1][j] ans = 0 for i in range(2, 901): if prime[i]: ans += dp[N][i] # Return the answer return ans# Driver codeif __name__ == '__main__': # Given input N = 6 # Function call print(countOfNumbers(N)) |
Javascript
// Function to generate all prime numbers// that are less than or equal to nfunction SieveOfEratosthenes(n, prime) { prime[0] = prime[1] = false; for (let p = 2; p * p <= n; p++) { if (prime[p] === true) { for (let i = p * p; i <= n; i += p) { prime[i] = false; } } }}// Function to find the count of N-digit numbers// such that the sum of digits is a prime numberfunction countOfNumbers(N) { // Stores the dp states const dp = new Array(N + 1).fill(null).map(() => new Array(1000).fill(0)); // Initializing prime array to true const prime = new Array(1005).fill(true); // Find all primes less than or equal to 1000, // which is sufficient for N upto 100 SieveOfEratosthenes(1000, prime); // Base cases for (let i = 1; i <= 9; i++) { dp[1][i] = 1; } if (N === 1) { dp[1][0] = 1; } // Fill the dp table for (let i = 2; i <= N; i++) { for (let j = 0; j <= 900; j++) { for (let k = 0; k <= 9; k++) { dp[i][j + k] += dp[i - 1][j]; } } } let ans = 0; for (let i = 2; i <= 900; i++) { if (prime[i]) { ans += dp[N][i]; } } // Return the answer return ans;}// Driver Codeconst N = 6;// Function callconsole.log(countOfNumbers(N)); |
Output:
222638
Time Complexity: O(N* 900 * 9)
Auxiliary Space: O(N*1000)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
