8

Count N-digit numbers having sum of digits equal to a Prime Number

 2 years ago
source link: https://www.geeksforgeeks.org/count-n-digit-numbers-having-sum-of-digits-equal-to-a-prime-number/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

Count N-digit numbers having sum of digits equal to a Prime Number

  • Last Updated : 28 Sep, 2021

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.
  • Print the value returned by the function countOfNumbers(1, 0, N) as the result.

Below is the implementation of the above approach:

  • Python3
  • Javascript
#include <bits/stdc++.h>
using namespace std;
// Stores the dp states
int dp[100][1000];
// Check if a number is
// a prime or not
bool prime[1005];
// Function to generate all prime numbers
// that are less than or equal to n
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 number
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 Code
int 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;
}
Output: 
222638

Time Complexity: O(N2 * 10)
Auxiliary Space: O(N2)


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK