Given an array Q[][] consisting of N queries of the form {L, R}, the task for each query is to find the count of the numbers in the range [L, R] that are palindrome and the sum of their digits is a prime number.
Examples:
Input: Q[][] = {{5, 9}, {5, 22}}
Output:
2
3
Explanation:
Query 1: All palindrome numbers from the range [5, 9] having sum of their digits equal to a prime number are {5, 7}. Therefore, the count of elements is 2.
Query 2: All palindrome numbers from the range [5, 20] having sum of their digits equal to a prime number are {5, 7, 11}. Therefore, the count of elements is 2.Input: Q[] = {{1, 101}, {13, 15}}
Output:
6
0
Naive Approach: The simplest approach to solve the given problem is to iterate over the range [L, R] for each query and print the count of those numbers that are palindrome, and the sum of their digits is a prime number.
Time Complexity: O(N*(R – L))
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized by using the Inclusion-Exclusion principle and the concepts of prefix sum. Follow the steps below to solve the given problem:
- Initialize an array arr[] to store the count of numbers up to each index i that are palindrome and the sum of their digits is a prime number at every ith index.
- Iterate over the range [1, 105], and for each element X, if the number X is palindromic and the sum of the digits is prime then update arr[i] to 1. Otherwise, set arr[i] = 0.
- Find the prefix sum array of the array arr[].
- Now, Traverse the array Q[] and for each query {L, R}, print the total count of the numbers in the range [L, R] that are palindrome and the sum of their digits is a prime number as (arr[R] – arr[L – 1]).
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;int arr[100005];// Function to check if the number N// is palindrome or notbool isPalindrome(int N){ // Store the value of N int temp = N; // Store the reverse of number N int res = 0; // Reverse temp and store in res while (temp != 0) { int rem = temp % 10; res = res * 10 + rem; temp /= 10; } // If N is the same as res, then // return true if (res == N) { return true; } else { return false; }}// Function to find the sum of the// digits of the number Nint sumOfDigits(int N){ // Stores the sum of the digits int sum = 0; while (N != 0) { // Add the last digit of the // number N to the sum sum += N % 10; // Remove the last digit // from N N /= 10; } // Return the resultant sum return sum;}// Function to check if N is prime or notbool isPrime(int n){ // If i is 1 or 0, then return false if (n <= 1) { return false; } // Check if i is divisible by any // number in the range [2, n/2] for (int i = 2; i <= n / 2; ++i) { // If n is divisible by i if (n % i == 0) return false; } return true;}// Function to precompute all the numbers// till 10^5 that are palindromic and// whose sum of digits is prime numbersvoid precompute(){ // Iterate over the range 1 to 10 ^ 5 for (int i = 1; i <= 100000; i++) { // If i is a palindrome number if (isPalindrome(i)) { // Stores the sum of // the digits in i int sum = sumOfDigits(i); // If the sum of digits // in i is a prime number if (isPrime(sum)) arr[i] = 1; else arr[i] = 0; } else arr[i] = 0; } // Find the prefix sum of arr[] for (int i = 1; i <= 100000; i++) { arr[i] = arr[i] + arr[i - 1]; }}// Function to count all the numbers in// the given ranges that are palindromic// and the sum of digits is prime numbersvoid countNumbers(int Q[][2], int N){ // Function Call to precompute // all the numbers till 10^5 precompute(); // Traverse the given queries Q[] for (int i = 0; i < N; i++) { // Print the result for // each query cout << (arr[Q[i][1]] - arr[Q[i][0] - 1]); cout << endl; }}// Driver Codeint main(){ int Q[][2] = { { 5, 9 }, { 1, 101 } }; int N = sizeof(Q) / sizeof(Q[0]); // Function Call countNumbers(Q, N);} |
Java
// Java program for the above approachclass GFG{ static int[] arr = new int[100005];// Function to check if the number N// is palindrome or notstatic boolean isPalindrome(int N){ int temp = N; // Store the reverse of number N int res = 0; // Reverse temp and store in res while (temp != 0) { int rem = temp % 10; res = res * 10 + rem; temp /= 10; } // If N is the same as res, then // return true if (res == N) { return true; } else { return false; }}// Function to find the sum of the// digits of the number Nstatic int sumOfDigits(int N){ // Stores the sum of the digits int sum = 0; while (N != 0) { // Add the last digit of the // number N to the sum sum += N % 10; // Remove the last digit // from N N /= 10; } // Return the resultant sum return sum;}// Function to check if N is prime or notstatic boolean isPrime(int n){ // If i is 1 or 0, then return false if (n <= 1) { return false; } // Check if i is divisible by any // number in the range [2, n/2] for(int i = 2; i <= n / 2; ++i) { // If n is divisible by i if (n % i == 0) return false; } return true;}// Function to precompute all the numbers// till 10^5 that are palindromic and// whose sum of digits is prime numbersstatic void precompute(){ // Iterate over the range 1 to 10 ^ 5 for(int i = 1; i <= 100000; i++) { // If i is a palindrome number if (isPalindrome(i)) { // Stores the sum of // the digits in i int sum = sumOfDigits(i); // If the sum of digits // in i is a prime number if (isPrime(sum)) arr[i] = 1; else arr[i] = 0; } else arr[i] = 0; } // Find the prefix sum of arr[] for(int i = 1; i <= 100000; i++) { arr[i] = arr[i] + arr[i - 1]; }}// Function to count all the numbers in// the given ranges that are palindromic// and the sum of digits is prime numbersstatic void countNumbers(int[][] Q, int N){ // Function Call to precompute // all the numbers till 10^5 precompute(); // Traverse the given queries Q[] for(int i = 0; i < N; i++) { // Print the result for // each query System.out.println((arr[Q[i][1]] - arr[Q[i][0] - 1])); }}// Driver Codepublic static void main(String[] args) { int[][] Q = { { 5, 9 }, { 1, 101 } }; int N = Q.length; // Function Call countNumbers(Q, N);}}// This code is contributed by user_qa7r |
Python3
# Python 3 program for the above approacharr = [0 for i in range(100005)]# Function to check if the number N# is palindrome or notdef isPalindrome(N): # Store the value of N temp = N # Store the reverse of number N res = 0 # Reverse temp and store in res while (temp != 0): rem = temp % 10 res = res * 10 + rem temp //= 10 # If N is the same as res, then # return true if (res == N): return True else: return False# Function to find the sum of the# digits of the number Ndef sumOfDigits(N): # Stores the sum of the digits sum = 0 while (N != 0): # Add the last digit of the # number N to the sum sum += N % 10 # Remove the last digit # from N N //= 10 # Return the resultant sum return sum# Function to check if N is prime or notdef isPrime(n): # If i is 1 or 0, then return false if (n <= 1): return False # Check if i is divisible by any # number in the range [2, n/2] for i in range(2, (n//2) + 1, 1): # If n is divisible by i if (n % i == 0): return False return True# Function to precompute all the numbers# till 10^5 that are palindromic and# whose sum of digits is prime numbersdef precompute(): # Iterate over the range 1 to 10 ^ 5 for i in range(1, 100001, 1): # If i is a palindrome number if (isPalindrome(i)): # Stores the sum of # the digits in i sum = sumOfDigits(i) # If the sum of digits # in i is a prime number if (isPrime(sum)): arr[i] = 1 else: arr[i] = 0 else: arr[i] = 0 # Find the prefix sum of arr[] for i in range(1,100001,1): arr[i] = arr[i] + arr[i - 1]# Function to count all the numbers in# the given ranges that are palindromic# and the sum of digits is prime numbersdef countNumbers(Q, N): # Function Call to precompute # all the numbers till 10^5 precompute() # Traverse the given queries Q[] for i in range(N): # Print the result for # each query print(arr[Q[i][1]] - arr[Q[i][0] - 1])# Driver Codeif __name__ == '__main__': Q = [[5, 9], [1, 101]] N = len(Q) # Function Call countNumbers(Q, N) # This code is contributed by bgangwar59. |
C#
// C# program for the above approachusing System;class GFG{static int[] arr = new int[100005];// Function to check if the number N// is palindrome or notstatic bool isPalindrome(int N){ int temp = N; // Store the reverse of number N int res = 0; // Reverse temp and store in res while (temp != 0) { int rem = temp % 10; res = res * 10 + rem; temp /= 10; } // If N is the same as res, then // return true if (res == N) { return true; } else { return false; }}// Function to find the sum of the// digits of the number Nstatic int sumOfDigits(int N){ // Stores the sum of the digits int sum = 0; while (N != 0) { // Add the last digit of the // number N to the sum sum += N % 10; // Remove the last digit // from N N /= 10; } // Return the resultant sum return sum;}// Function to check if N is prime or notstatic bool isPrime(int n){ // If i is 1 or 0, then return false if (n <= 1) { return false; } // Check if i is divisible by any // number in the range [2, n/2] for(int i = 2; i <= n / 2; ++i) { // If n is divisible by i if (n % i == 0) return false; } return true;}// Function to precompute all the numbers// till 10^5 that are palindromic and// whose sum of digits is prime numbersstatic void precompute(){ // Iterate over the range 1 to 10 ^ 5 for(int i = 1; i <= 100000; i++) { // If i is a palindrome number if (isPalindrome(i)) { // Stores the sum of // the digits in i int sum = sumOfDigits(i); // If the sum of digits // in i is a prime number if (isPrime(sum)) arr[i] = 1; else arr[i] = 0; } else arr[i] = 0; } // Find the prefix sum of arr[] for(int i = 1; i <= 100000; i++) { arr[i] = arr[i] + arr[i - 1]; }}// Function to count all the numbers in// the given ranges that are palindromic// and the sum of digits is prime numbersstatic void countNumbers(int[, ] Q, int N){ // Function Call to precompute // all the numbers till 10^5 precompute(); // Traverse the given queries Q[] for(int i = 0; i < N; i++) { // Print the result for // each query Console.WriteLine((arr[Q[i, 1]] - arr[Q[i, 0] - 1])); }}// Driver Codestatic public void Main(){ int[,] Q = { { 5, 9 }, { 1, 101 } }; int N = Q.GetLength(0); // Function Call countNumbers(Q, N);}}// This code is contributed by Dharanendra L V. |
Javascript
<script>// JavaScript program for the above approachlet arr = [];for(let m = 0; m < 100005; m++){ arr[m] = 0;} // Function to check if the number N// is palindrome or notfunction isPalindrome(N){ let temp = N; // Store the reverse of number N let res = 0; // Reverse temp and store in res while (temp != 0) { let rem = temp % 10; res = res * 10 + rem; temp = Math.floor( temp / 10); } // If N is the same as res, then // return true if (res == N) { return true; } else { return false; }} // Function to find the sum of the// digits of the number Nfunction sumOfDigits(N){ // Stores the sum of the digits let sum = 0; while (N != 0) { // Add the last digit of the // number N to the sum sum += N % 10; // Remove the last digit // from N N = Math.floor( N / 10); } // Return the resultant sum return sum;} // Function to check if N is prime or notfunction isPrime(n){ // If i is 1 or 0, then return false if (n <= 1) { return false; } // Check if i is divisible by any // number in the range [2, n/2] for(let i = 2; i <= Math.floor(n / 2); ++i) { // If n is divisible by i if (n % i == 0) return false; } return true;} // Function to precompute all the numbers// till 10^5 that are palindromic and// whose sum of digits is prime numbersfunction precompute(){ // Iterate over the range 1 to 10 ^ 5 for(let i = 1; i <= 100000; i++) { // If i is a palindrome number if (isPalindrome(i)) { // Stores the sum of // the digits in i let sum = sumOfDigits(i); // If the sum of digits // in i is a prime number if (isPrime(sum)) arr[i] = 1; else arr[i] = 0; } else arr[i] = 0; } // Find the prefix sum of arr[] for(let i = 1; i <= 100000; i++) { arr[i] = arr[i] + arr[i - 1]; }} // Function to count all the numbers in// the given ranges that are palindromic// and the sum of digits is prime numbersfunction countNumbers( Q, N){ // Function Call to precompute // all the numbers till 10^5 precompute(); // Traverse the given queries Q[] for(let i = 0; i < N; i++) { // Print the result for // each query document.write((arr[Q[i][1]] - arr[Q[i][0] - 1]) + "<br/>"); }}// Driver Code let Q = [[ 5, 9 ], [ 1, 101 ]]; let N = Q.length; // Function Call countNumbers(Q, N); </script> |
Output:
2 6
Time Complexity: O(N*log N)
Auxiliary Space: O(M), where M is the maximum element among each query.
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!
