Sum of all palindromic numbers lying in the range [L, R] for Q queries

0 0 7 minutes read

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
// number
long long pref[100001];
 
// Function that return number
// num if num is palindromic
// else return 0
int 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 100000
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 query
void 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 code
int 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 range
import java.util.*;
 
class GFG{
  
// pref[] array to precompute
// the sum of all palindromic
// number
static int []pref = new int[100001];
  
// Function that return number
// num if num is palindromic
// else return 0
static 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 100000
static 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 query
static 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 code
public 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
# number
pref=[0]*100001
 
# Function that return number
# num if num is palindromic
# else return 0
def 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 100000
def 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 query
def 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
 
# Queries
Q = 2
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 shivanisinghss2110

C#

// C# program to find the sum
// of all palindrome numbers
// in the given range
using System;
 
class GFG{
   
// pref[] array to precompute
// the sum of all palindromic
// number
static int []pref = new int[100001];
   
// Function that return number
// num if num is palindromic
// else return 0
static 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 100000
static 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 query
static 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 code
public 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
// number
var pref=Array(100001).fill(0);
 
// Function that return number
// num if num is palindromic
// else return 0
function 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 100000
function 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 query
function 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
 
// Queries
var 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+10⁵)
Auxiliary Space: O(10⁵)

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 zambiatek!