Given Q queries in the form of 2D array arr[][] whose every row consists of two numbers L and R which denotes the range [L, R], the task is to find the sum of all Palindrome Numbers lying in range [L, R].
Input: Q = 2, arr[][] = { {10, 13}, {12, 21} }
Output:
11
0
Explanation:
From 10 to 13 only 11 is the palindrome number
From 12 to 21 there is no palindromic number
Input: Q = 4, arr[][] = { { 10, 10 }, { 258, 785 }, {45, 245 }, { 1, 1000} }
Output:
0
27024
2955
50040
Approach:
The idea is to use the prefix sum array. The sum of all palindromic number till that particular index is precomputed and stored in an array pref[] so that every query can be answered in O(1) time.
- Initialise the prefix array pref[].
- Iterate from 1 to N and check if the number is palindromic or not:
- If the number is palindromic then, the current index of pref[] will store the sum of the number and the number at previous index of pref[].
- Else the current index of pref[] is same as the value at previous index of pref[].
- For Q queries the sum of all palindromic numbers for range [L, R] can be found as follows:
sum = pref[R] - pref[L - 1]
Below is the implementation of the above approach
C++
// C++ program to find the sum// of all palindrome numbers// in the given range#include <bits/stdc++.h>using namespace std;// pref[] array to precompute// the sum of all palindromic// numberlong long pref[100001];// Function that return number// num if num is palindromic// else return 0int checkPalindrome(int num){ // Convert num to string string str = to_string(num); int l = 0, r = str.length() - 1; while (l < r) { if (str[l] != str[r]) { return 0; } l++; r--; } return num;}// Function to precompute the// sum of all palindrome numbers// upto 100000void preCompute(){ for (int i = 1; i <= 100000; ++i) { // checkPalindrome() // return the number i // if i is palindromic // else return 0 pref[i] = pref[i - 1] + checkPalindrome(i); }}// Function to print the sum// for each queryvoid printSum(int L, int R){ cout << pref[R] - pref[L - 1] << endl;}// Function to print sum of all// palindromic numbers between// [L, R]void printSumPalindromic(int arr[][2], int Q){ // Function that pre computes // the sum of all palindromic // numbers preCompute(); // Iterate over all Queries // to print the sum for (int i = 0; i < Q; i++) { printSum(arr[i][0], arr[i][1]); }}// Driver codeint main(){ // Queries int Q = 2; int arr[][2] = { { 10, 13 }, { 12, 21 } }; // Function that print the // the sum of all palindromic // number in Range [L, R] printSumPalindromic(arr, Q); return 0;} |
Java
// Java program to find the sum// of all palindrome numbers// in the given rangeimport java.util.*;class GFG{ // pref[] array to precompute// the sum of all palindromic// numberstatic int []pref = new int[100001]; // Function that return number// num if num is palindromic// else return 0static int checkPalindrome(int num){ // Convert num to String String str = String.valueOf(num); int l = 0, r = str.length() - 1; while (l < r) { if (str.charAt(l) != str.charAt(r)) { return 0; } l++; r--; } return num;} // Function to precompute the// sum of all palindrome numbers// upto 100000static void preCompute(){ for (int i = 1; i <= 100000; ++i) { // checkPalindrome() // return the number i // if i is palindromic // else return 0 pref[i] = pref[i - 1] + checkPalindrome(i); }} // Function to print the sum// for each querystatic void printSum(int L, int R){ System.out.print(pref[R] - pref[L - 1] +"\n");} // Function to print sum of all// palindromic numbers between// [L, R]static void printSumPalindromic(int arr[][], int Q){ // Function that pre computes // the sum of all palindromic // numbers preCompute(); // Iterate over all Queries // to print the sum for (int i = 0; i < Q; i++) { printSum(arr[i][0], arr[i][1]); }} // Driver codepublic static void main(String[] args){ // Queries int Q = 2; int arr[][] = { { 10, 13 }, { 12, 21 } }; // Function that print the // the sum of all palindromic // number in Range [L, R] printSumPalindromic(arr, Q);}}// This code is contributed by 29AjayKumar |
Python3
# Python3 program to find the sum# of all palindrome numbers# in the given range# pref[] array to precompute# the sum of all palindromic# numberpref=[0]*100001# Function that return number# num if num is palindromic# else return 0def checkPalindrome(num): # Convert num to string strr = str(num) l = 0 r = len(strr)- 1 while (l < r): if (strr[l] != strr[r]): return 0 l+=1 r-=1 return num# Function to precompute the# sum of all palindrome numbers# upto 100000def preCompute(): for i in range(1,100001): # checkPalindrome() # return the number i # if i is palindromic # else return 0 pref[i] = pref[i - 1]+ checkPalindrome(i) # Function to print the sum# for each querydef printSum(L, R): print(pref[R] - pref[L - 1])# Function to print sum of all# palindromic numbers between# [L, R]def printSumPalindromic(arr,Q): # Function that pre computes # the sum of all palindromic # numbers preCompute() # Iterate over all Queries # to print the sum for i in range(Q): printSum(arr[i][0], arr[i][1]) # Driver code# QueriesQ = 2arr= [[10, 13 ],[ 12, 21 ]]# Function that print the# the sum of all palindromic# number in Range [L, R]printSumPalindromic(arr, Q)# This code is contributed by shivanisinghss2110 |
C#
// C# program to find the sum// of all palindrome numbers// in the given rangeusing System;class GFG{ // pref[] array to precompute// the sum of all palindromic// numberstatic int []pref = new int[100001]; // Function that return number// num if num is palindromic// else return 0static int checkPalindrome(int num){ // Convert num to String String str = String.Join("",num); int l = 0, r = str.Length - 1; while (l < r) { if (str[l] != str[r]) { return 0; } l++; r--; } return num;} // Function to precompute the// sum of all palindrome numbers// upto 100000static void preCompute(){ for (int i = 1; i <= 100000; ++i) { // checkPalindrome() // return the number i // if i is palindromic // else return 0 pref[i] = pref[i - 1] + checkPalindrome(i); }} // Function to print the sum// for each querystatic void printSum(int L, int R){ Console.Write(pref[R] - pref[L - 1] +"\n");} // Function to print sum of all// palindromic numbers between// [L, R]static void printSumPalindromic(int [,]arr, int Q){ // Function that pre computes // the sum of all palindromic // numbers preCompute(); // Iterate over all Queries // to print the sum for (int i = 0; i < Q; i++) { printSum(arr[i,0], arr[i,1]); }} // Driver codepublic static void Main(String[] args){ // Queries int Q = 2; int [,]arr = { { 10, 13 }, { 12, 21 } }; // Function that print the // the sum of all palindromic // number in Range [L, R] printSumPalindromic(arr, Q);}}// This code is contributed by PrinciRaj1992 |
Javascript
<script>// Javascript program to find the sum// of all palindrome numbers// in the given range// pref[] array to precompute// the sum of all palindromic// numbervar pref=Array(100001).fill(0);// Function that return number// num if num is palindromic// else return 0function checkPalindrome(num){ // Convert num to string var str = num.toString(); var l = 0, r = str.length - 1; while (l < r) { if (str[l] != str[r]) { return 0; } l++; r--; } return num;}// Function to precompute the// sum of all palindrome numbers// upto 100000function preCompute(){ for (var i = 1; i <= 100000; ++i) { // checkPalindrome() // return the number i // if i is palindromic // else return 0 pref[i] = pref[i - 1] + checkPalindrome(i); }}// Function to print the sum// for each queryfunction printSum(L, R){ document.write( pref[R] - pref[L - 1]+"<br>");}// Function to print sum of all// palindromic numbers between// [L, R]function printSumPalindromic(arr, Q){ // Function that pre computes // the sum of all palindromic // numbers preCompute(); // Iterate over all Queries // to print the sum for (var i = 0; i < Q; i++) { printSum(arr[i][0], arr[i][1]); }}// Driver code// Queriesvar Q = 2;var arr = [ [ 10, 13 ], [ 12, 21 ] ];// Function that print the// the sum of all palindromic// number in Range [L, R]printSumPalindromic(arr, Q);</script> |
Output:
11 0
Time Complexity: O(Q+105)
Auxiliary Space: O(105)
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!
… [Trackback]
[…] Read More on to that Topic: geeksforgeeks.org/sum-of-all-palindromic-numbers-lying-in-the-range-l-r-for-q-queries/ […]