Suma de todos los números palindrómicos que se encuentran en el rango [L, R] para consultas Q

Posted on by Rudeus Greyrat

Dadas las consultas Q en forma de array 2D arr[][] cuyas filas consisten en dos números L y R que denotan el rango [L, R], la tarea es encontrar la suma de todos los números palíndromos que se encuentran en el rango [L , R] .
 

Entrada: Q = 2, arr[][] = { {10, 13}, {12, 21} } 
Salida: 
11 
0 
Explicación: 
Del 10 al 13 solo el 11 es el número palíndromo 
Del 12 al 21 no hay número palindrómico
Entrada: Q = 4, arr[][] = { { 10, 10 }, { 258, 785 }, {45, 245 }, { 1, 1000} } 
Salida: 
0 
27024 
2955 
50040 
 

Enfoque: 
La idea es usar la array de suma de prefijos . La suma de todos los números palindrómicos hasta ese índice en particular se calcula previamente y se almacena en una array pref[] para que cada consulta se pueda responder en tiempo O(1) . 
 

  1. Inicialice la array de prefijos pref[] .
  2. Iterar de 1 a N y verificar si el número es palindrómico o no: 
    • Si el número es palindrómico, el índice actual de pref[] almacenará la suma del número y el número en el índice anterior de pref[] .
    • De lo contrario, el índice actual de pref[] es el mismo que el valor en el índice anterior de pref[] .
  3. Para consultas Q , la suma de todos los números palindrómicos para el rango [L, R] se puede encontrar de la siguiente manera: 
     
sum = pref[R] - pref[L - 1]
  1.  

A continuación se muestra la implementación del enfoque anterior. 
 

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>
Producción: 

11
0

 

Complejidad de Tiempo: O(N)
 Espacio Auxiliar: O(10 5 )

Publicación traducida automáticamente

Artículo escrito por spp____ y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *