Given two integers L and R, the task is to count all the numbers in the range [L, R] whose sum of digits is a prime number.
Examples:
Input: L = 1, R = 10
Output: 4
Explanation:
Numbers in the range L(= 1) to R(= 10), whose sum of digits is a prime number are {2, 3, 5, 7}. Therefore, the required output is 4.Input: L = 11, R = 999
Output: 336
Naive Approach: The simplest approach to solve this problem is to traverse all the numbers in the range [L, R] and for each number, check if the sum of digits of the number is a prime number or not. If found to be true, increment the count and finally, print the count as the required answer.
Time Complexity: O((R – L + 1) * sqrt(R))
Auxiliary Space: O(1)
Efficient Approach: The problem can be solved using Digit DP. The idea is to count the numbers in the range [1, R] whose sum of digits is a prime number and subtract the count of the numbers in the range [1, L – 1] whose sum of digits is a prime number.
The following are the recurrence relations:
[Tex]= \sum^{9}_{i=0} cnt1XPrime(sum + i, len + 1, tight \& (i==end)) [/Tex]
cnt1XPrime(sum, len, tight): Stores the count of numbers in the range [1, X] with the following constraints:
sum= Stores sum of digits of a number in the range [1, X].
len = count of digits in X.
tight = Boolean value to check if the current digits range is restricted or not.
[Tex]= \sum^{9}_{i=0} cnt1XPrime(sum + i, len + 1, tight \& (i==end)) [/Tex]Follow the steps below to solve the problem:
- Initialize a 3D array dp[sum][len][tight] to compute and store the values of all subproblems of the above recurrence relation.
- Finally, return the value of dp[sum][len][tight].
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to find all prime numbers// in the range [1, 100000] using// Sieve of Eratosthenes techniquevector<bool> sieve(){ // isPrime[i] stores if i // is a prime number or not. vector<bool> isPrime(100001, true); // 0 is not a prime number isPrime[0] = false; // 1 is not prime number isPrime[1] = false; // Traverse the range to check if // i is a prime number or not for (int i = 2; i * i < 100001; i++) { // If i is a prime number if (isPrime[i]) { for (int j = i * i; j < 100001; j += i) { // Mark its multiples non-prime isPrime[j] = false; } } } return isPrime;}// Function to count all numbers in// the range[1, X] whose sum of digits// is a prime numberint cnt1XPrime(int sum, int len, bool tight, string X, vector<bool>& isPrime, int dp[1000][100][2]){ // If count of digits in current number // is equal to the count of digits in X if (len == X.length()) { // If sum is a prime number return isPrime[sum]; } // If already computed subproblem // occurred if (dp[sum][len][tight] != -1) { return dp[sum][len][tight]; } // Stores maximum possible value // at current digit of the number int end = tight ? (X[len] - '0') : 9; // Stores count of numbers by placing // all possible values at current index int res = 0; // Place all possible values at // current position for (int i = 0; i <= end; i++) { // Update res res += cnt1XPrime(sum + i, len + 1, (tight & (i == end)), X, isPrime, dp); } dp[sum][len][tight]=res; return res;}// Function to count the numbers in// the range[L, R]int cntLRprime(int L, int R){ // Stores the value of (L - 1) // in the form of string string LStr = to_string(L - 1); // Stores the value of (R) // in the form of string string RStr = to_string(R); // Stores values of overlapping // subproblems int dp[1000][100][2]; // Initialize dp[][][] array memset(dp, -1, sizeof(dp)); // isPrime[i] stores if i // is a prime number or not vector<bool> isPrime = sieve(); // Stores count of numbers in range // [1, LStr] with the given conditions int cntL = cnt1XPrime(0, 0, 1, LStr, isPrime, dp); // Initialize dp[][][] array. memset(dp, -1, sizeof(dp)); // Stores count of numbers in range // [1, RStr] with the given conditions int cntR = cnt1XPrime(0, 0, 1, RStr, isPrime, dp); // Return numbers in the range [L, R] // whose sum of digits is a prime number return (cntR - cntL);}// Driver Codeint main(){ int L = 11, R = 999; cout << cntLRprime(L, R); return 0;} |
Java
// Java program to implement// the above approachimport java.util.*;class solution { // Function to find all prime // numbers in the range [1, 100000] // using Sieve of Eratosthenes // technique static boolean[] sieve() { // isPrime[i] stores if i // is a prime number or not boolean[] isPrime = new boolean[100001]; for (int i = 0; i < 100001; i++) isPrime[i] = true; // 0 is not a prime number isPrime[0] = false; // 1 is not prime number isPrime[1] = false; // Traverse the range to check if // i is a prime number or not for (int i = 2; i * i < 100001; i++) { // If i is a prime number if (isPrime[i] == true) { for (int j = i * i; j < 100001; j += i) { // Mark its multiples // non-prime isPrime[j] = false; } } } return isPrime; } // Function to count all numbers in // the range[1, X] whose sum of digits // is a prime number static int cnt1XPrime(int sum, int len, int tight, String X, boolean[] isPrime, int[][][] dp) { // If count of digits in current // number is equal to the count of // digits in X if (len == X.length()) { // If sum is a prime number return isPrime[sum] ? 1 : 0; } // If already computed subproblem // occurred if (dp[sum][len][tight] != -1) { return dp[sum][len][tight]; } // Stores maximum possible value // at current digit of the number int end = (tight == 1) ? (X.charAt(len) - 48) : 9; // Stores count of numbers by // placing all possible values // at current index int res = 0; // Place all possible values at // current position for (int i = 0; i <= end; i++) { // Update res res += cnt1XPrime( sum + i, len + 1, (tight & ((i == end) ? 1 : 0)), X, isPrime, dp); } return dp[sum][len][tight] = res; } // Function to count the numbers in // the range[L, R] static int cntLRprime(int L, int R) { // Stores the value of (L - 1) // in the form of string String LStr = String.valueOf(L - 1); // Stores the value of (R) // in the form of string String RStr = String.valueOf(R); // Stores values of overlapping // subproblems int[][][] dp = new int[1000][100][2]; // Initialize dp[][][] array for (int i = 0; i < 1000; i++) { for (int j = 0; j < 100; j++) { for (int k = 0; k < 2; k++) dp[i][j][k] = -1; } } // isPrime[i] stores if i // is a prime number or not boolean[] isPrime = sieve(); // Stores count of numbers in // range [1, LStr] with the // given conditions int cntL = cnt1XPrime(0, 0, 1, LStr, isPrime, dp); // Initialize dp[][][] array. for (int i = 0; i < 1000; i++) { for (int j = 0; j < 100; j++) { for (int k = 0; k < 2; k++) dp[i][j][k] = -1; } } // Stores count of numbers in range // [1, RStr] with the given conditions int cntR = cnt1XPrime(0, 0, 1, RStr, isPrime, dp); // Return numbers in the range // [L, R] whose sum of digits // is a prime number return (cntR - cntL); } // Driver Code public static void main(String args[]) { int L = 11, R = 999; System.out.print(cntLRprime(L, R)); }}// This code is contributed by SURENDRA_GANGWAR |
Python3
# Python3 program to implement# the above approachisPrime = [True] * 100001dp = [[[-1 for i in range(2)] for i in range(100)] for i in range(1000)]# Function to find all prime numbers# in the range [1, 100000] using# Sieve of Eratosthenes techniquedef sieve(): # 0 is not a prime number isPrime[0] = False # 1 is not prime number isPrime[1] = False # Traverse the range to check if # i is a prime number or not for i in range(2, 100001): if i * i > 100001: break # If i is a prime number if (isPrime[i]): for j in range(i * i, 100001, i): # Mark its multiples non-prime isPrime[j] = False# Function to count all numbers in# the range[1, X] whose sum of digits# is a prime numberdef cnt1XPrime(sUm, lenn, tight, X): # If count of digits in current number # is equal to the count of digits in X if (lenn == len(X)): # If sum is a prime number return isPrime[sUm] # If already computed subproblem # occurred if (dp[sUm][lenn][tight] != -1): return dp[sUm][lenn][tight] # Stores maximum possible value # at current digit of the number end = 9 if tight: end = ord(X[lenn]) - ord('0') # Stores count of numbers by placing # all possible values at current index res = 0 # Place all possible values at # current position for i in range(end + 1): # Update res res += cnt1XPrime(sUm + i, lenn + 1, (tight & (i == end)), X) dp[sUm][lenn][tight] = res return res# Function to count the numbers in# the range[L, R]def cntLRprime(L, R): # Stores the value of (L - 1) # in the form of string LStr = str(L - 1) # Stores the value of (R) # in the form of string RStr = str(R) # isPrime[i] stores if i # is a prime number or not sieve() # Stores count of numbers in range # [1, LStr] with the given conditions cntL = cnt1XPrime(0, 0, 1, LStr) # Initialize dp[][][] array. for i in range(1000): for j in range(100): for z in range(2): dp[i][j][z] = -1 # Stores count of numbers in range # [1, RStr] with the given conditions cntR = cnt1XPrime(0, 0, 1, RStr) # Return numbers in the range [L, R] # whose sum of digits is a prime number return (cntR - cntL)# Driver codeif __name__ == '__main__': L = 11 R = 999 print(cntLRprime(L, R))# This code is contributed by mohit kumar 29 |
C#
// C# program to implement// the above approachusing System;class GFG { // Function to find all prime // numbers in the range [1, 100000] // using Sieve of Eratosthenes // technique static bool[] sieve() { // isPrime[i] stores if i // is a prime number or not bool[] isPrime = new bool[100001]; for (int i = 0; i < 100001; i++) isPrime[i] = true; // 0 is not a prime // number isPrime[0] = false; // 1 is not prime // number isPrime[1] = false; // Traverse the range to // check if i is a prime // number or not for (int i = 2; i * i < 100001; i++) { // If i is a prime number if (isPrime[i] == true) { for (int j = i * i; j < 100001; j += i) { // Mark its multiples // non-prime isPrime[j] = false; } } } return isPrime; } // Function to count all numbers // in the range[1, X] whose sum // of digits is a prime number static int cnt1XPrime(int sum, int len, int tight, String X, bool[] isPrime, int[, , ] dp) { // If count of digits in current // number is equal to the count of // digits in X if (len == X.Length) { // If sum is a prime number return isPrime[sum] ? 1 : 0; } // If already computed // subproblem occurred if (dp[sum, len, tight] != -1) { return dp[sum, len, tight]; } // Stores maximum possible value // at current digit of the number int end = (tight == 1) ? (X[len] - 48) : 9; // Stores count of numbers by // placing all possible values // at current index int res = 0; // Place all possible values at // current position for (int i = 0; i <= end; i++) { // Update res res += cnt1XPrime( sum + i, len + 1, (tight & ((i == end) ? 1 : 0)), X, isPrime, dp); } return dp[sum, len, tight] = res; } // Function to count the numbers in // the range[L, R] static int cntLRprime(int L, int R) { // Stores the value of (L - 1) // in the form of string string LStr = (L - 1).ToString(); // Stores the value of (R) // in the form of string string RStr = (R).ToString(); // Stores values of overlapping // subproblems int[, , ] dp = new int[1000, 100, 2]; // Initialize dp[][][] array for (int i = 0; i < 1000; i++) { for (int j = 0; j < 100; j++) { for (int k = 0; k < 2; k++) dp[i, j, k] = -1; } } // isPrime[i] stores if i // is a prime number or not bool[] isPrime = sieve(); // Stores count of numbers in // range [1, LStr] with the // given conditions int cntL = cnt1XPrime(0, 0, 1, LStr, isPrime, dp); // Initialize dp[][][] array. for (int i = 0; i < 1000; i++) { for (int j = 0; j < 100; j++) { for (int k = 0; k < 2; k++) dp[i, j, k] = -1; } } // Stores count of numbers in // range [1, RStr] with the // given conditions int cntR = cnt1XPrime(0, 0, 1, RStr, isPrime, dp); // Return numbers in the range // [L, R] whose sum of digits // is a prime number return (cntR - cntL); } // Driver Code public static void Main(String[] args) { int L = 11, R = 999; Console.Write(cntLRprime(L, R)); }}// This code is contributed by Chitranayal |
Javascript
<script>// Javascript program to implement// the above approach// Function to find all prime// numbers in the range [1, 100000]// using Sieve of Eratosthenes// techniquefunction sieve(){ // isPrime[i] stores if i // is a prime number or not let isPrime = new Array(100001); for(let i = 0; i < 100001; i++) isPrime[i] = true; // 0 is not a prime number isPrime[0] = false; // 1 is not prime number isPrime[1] = false; // Traverse the range to check if // i is a prime number or not for(let i = 2; i * i < 100001; i++) { // If i is a prime number if (isPrime[i] == true) { for(let j = i * i; j < 100001; j += i) { // Mark its multiples // non-prime isPrime[j] = false; } } } return isPrime;}// Function to count all numbers in// the range[1, X] whose sum of digits// is a prime numberfunction cnt1XPrime(sum, len, tight, X, isPrime, dp){ // If count of digits in current // number is equal to the count of // digits in X if (len == X.length) { // If sum is a prime number return isPrime[sum] ? 1 : 0; } // If already computed subproblem // occurred if (dp[sum][len][tight] != -1) { return dp[sum][len][tight]; } // Stores maximum possible value // at current digit of the number let end = (tight == 1) ? (X[len].charCodeAt(0) - 48) : 9; // Stores count of numbers by // placing all possible values // at current index let res = 0; // Place all possible values at // current position for(let i = 0; i <= end; i++) { // Update res res += cnt1XPrime(sum + i, len + 1, (tight & ((i == end) ? 1 : 0)), X, isPrime, dp); } return dp[sum][len][tight] = res;}// Function to count the numbers in// the range[L, R]function cntLRprime(L, R){ // Stores the value of (L - 1) // in the form of string let LStr = (L - 1).toString(); // Stores the value of (R) // in the form of string let RStr = (R).toString(); // Stores values of overlapping // subproblems let dp = new Array(1000); // Initialize dp[][][] array for(let i = 0; i < 1000; i++) { dp[i] = new Array(100); for(let j = 0; j < 100; j++) { dp[i][j] = new Array(2); for(let k = 0; k < 2; k++) dp[i][j][k] = -1; } } // isPrime[i] stores if i // is a prime number or not let isPrime = sieve(); // Stores count of numbers in // range [1, LStr] with the // given conditions let cntL = cnt1XPrime(0, 0, 1, LStr, isPrime, dp); // Initialize dp[][][] array. for(let i = 0; i < 1000; i++) { for(let j = 0; j < 100; j++) { for(let k = 0; k < 2; k++) dp[i][j][k] = -1; } } // Stores count of numbers in range // [1, RStr] with the given conditions let cntR = cnt1XPrime(0, 0, 1, RStr, isPrime, dp); // Return numbers in the range // [L, R] whose sum of digits // is a prime number return (cntR - cntL);}// Driver Codelet L = 11, R = 999;document.write(cntLRprime(L, R));// This code is contributed by avanitrachhadiya2155</script> |
Output
336
Time Complexity: O(sum * M * 10)
Auxiliary Space: O(sum * M), where sum denotes the maximum sum of digits of a number in the range [L, R] and M denotes the number of digits in R.
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!
