Dada una array Q[][] que consta de N consultas de la forma {L, R} , la tarea de cada consulta es encontrar el recuento total de números del rango [L, R] , cuyo cubo es un palíndromo .
Ejemplos:
Entrada: Q[][] = {{2, 10}, {10, 20}}
Salida:
2
1
Explicación:
Consulta 1: Los números del rango [2, 10], cuyo cubo es un palíndromo son 2, 7
Consulta 2: El único número del rango [10, 20], cuyo cubo es un palíndromo es 11Entrada: Q[][] = {{1, 50}, {13, 15}}
Salida:
4
0
Explicación:
Consulta 1: Los números del rango [1, 50], cuyo cubo es un palíndromo son {1, 2, 7, 11}.
Consulta 2: No existe tal número en el rango [13, 15].
Enfoque: la idea más simple para resolver el problema es utilizar el principio de inclusión-exclusión y la técnica de array de suma de prefijos para resolver este problema. Siga los pasos a continuación para resolver el problema dado:
- Inicialice una array arr[] , para almacenar en cada i -ésimo índice, ya sea que el cubo de i sea un palíndromo o no .
- Recorra la array arr[] y para cada i -ésimo índice, verifique si i es un palíndromo o no .
- Si se encuentra que es cierto, establezca arr[i] = 1 .
- De lo contrario, establezca arr[i] = 0 .
- Convierta la array arr[] en una array de suma de prefijos .
- Recorre la array Q[][] y cuenta el número del rango [L, R] cuyo cubo es un palíndromo calculando arr[R] – arr[L-1] .
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program of the above approach
#include <bits/stdc++.h>
using namespace std;
int arr[10005];
// Function to check if n is
// a pallindrome number or not
int isPalindrome(int n)
{
// Temporarily store n
int temp = n;
// Stores reverse of n
int res = 0;
// Iterate until temp reduces to 0
while (temp != 0) {
// Extract the last digit
int rem = temp % 10;
// Add to the start
res = res * 10 + rem;
// Remove the last digit
temp /= 10;
}
// If the number and its
// reverse are equal
if (res == n) {
return 1;
}
// Otherwise
else
return 0;
}
// Function to precompute and store
// the count of numbers whose cube
// is a palindrome number
void precompute()
{
// Iterate upto 10^4
for (int i = 1; i <= 10000; i++) {
// Check if i*i*i is a
// pallindrome or not
if (isPalindrome(i * i * i))
arr[i] = 1;
else
arr[i] = 0;
}
// Convert arr[] to prefix sum array
for (int i = 1; i <= 10000; i++) {
arr[i] = arr[i] + arr[i - 1];
}
}
// Driver Code
int main()
{
// Given queries
vector<pair<int, int> > Q = { { 2, 7 }, { 10, 25 } };
precompute();
for (auto it : Q) {
// Using inclusion-exclusion
// principle, count required numbers
cout << arr[it.second] - arr[it.first - 1] << "\n";
}
return 0;
}
Java
// Java program of the above approach
import java.io.*;
import java.util.*;
public class Pair {
private final int key;
private final int value;
public Pair(int aKey, int aValue)
{
key = aKey;
value = aValue;
}
public int key() { return key; }
public int value() { return value; }
}
class GFG {
static int[] arr = new int[10005];
// Function to check if n is
// a pallindrome number or not
static int isPalindrome(int n)
{
// Temporarily store n
int temp = n;
// Stores reverse of n
int res = 0;
// Iterate until temp reduces to 0
while (temp != 0)
{
// Extract the last digit
int rem = temp % 10;
// Add to the start
res = res * 10 + rem;
// Remove the last digit
temp /= 10;
}
// If the number and its
// reverse are equal
if (res == n) {
return 1;
}
// Otherwise
else
return 0;
}
// Function to precompute and store
// the count of numbers whose cube
// is a palindrome number
static void precompute()
{
// Iterate upto 10^4
for (int i = 1; i <= 10000; i++) {
// Check if i*i*i is a
// pallindrome or not
if (isPalindrome(i * i * i)!= 0)
arr[i] = 1;
else
arr[i] = 0;
}
// Convert arr[] to prefix sum array
for (int i = 1; i <= 10000; i++) {
arr[i] = arr[i] + arr[i - 1];
}
}
// Driver Code
public static void main(String[] args)
{
// Given queries
ArrayList<Pair> Q = new ArrayList<Pair>();
Pair pair = new Pair(2, 7);
Q.add(pair);
Pair pair2 = new Pair(10, 25);
Q.add(pair2);
precompute();
for (int i = 0; i < Q.size(); i++) {
// Using inclusion-exclusion
// principle, count required numbers
System.out.println(arr[Q.get(i).value()] - arr[Q.get(i).key()-1]);
}
}
}
// This code is contributed by Dharanendra L V
Javascript
<script>
// Javascript program of the above approach
let arr = new Array(10005).fill(0)
// Function to check if n is
// a pallindrome number or not
function isPalindrome(n) {
// Temporarily store n
let temp = n;
// Stores reverse of n
let res = 0;
// Iterate until temp reduces to 0
while (temp != 0) {
// Extract the last digit
let rem = temp % 10;
// Add to the start
res = res * 10 + rem;
// Remove the last digit
temp = Math.floor(temp / 10);
}
// If the number and its
// reverse are equal
if (res == n) {
return 1;
}
// Otherwise
else
return 0;
}
// Function to precompute and store
// the count of numbers whose cube
// is a palindrome number
function precompute() {
// Iterate upto 10^4
for (let i = 1; i <= 10000; i++) {
// Check if i*i*i is a
// pallindrome or not
if (isPalindrome(i * i * i))
arr[i] = 1;
else
arr[i] = 0;
}
// Convert arr[] to prefix sum array
for (let i = 1; i <= 10000; i++) {
arr[i] = arr[i] + arr[i - 1];
}
}
// Driver Code
// Given queries
let Q = [[2, 7], [10, 25]];
precompute();
for (let it of Q) {
// Using inclusion-exclusion
// principle, count required numbers
document.write(arr[it[1]] - arr[it[0] - 1] + "<br>");
}
// This code is contributed by saurabh_jaiswal.
</script>
2 1
Complejidad de tiempo: O(N)
Espacio auxiliar: O(maxm), donde maxm denota el valor máximo de R en una consulta
Publicación traducida automáticamente
Artículo escrito por patelajeet y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA