Dada una array Q[][] que consta de N consultas de la forma {L, R} , la tarea de cada consulta es encontrar el recuento de los números en el rango [L, R] que son palíndromos y la suma de sus dígitos es un número primo .
Ejemplos:
Entrada: Q[][] = {{5, 9}, {5, 22}}
Salida:
2
3
Explicación:
Consulta 1: Todos los números palíndromos del rango [5, 9] que tienen la suma de sus dígitos igual a un número primo número son {5, 7}. Por lo tanto, el conteo de elementos es 2.
Consulta 2: Todos los números palíndromos del rango [5, 20] que tienen la suma de sus dígitos igual a un número primo son {5, 7, 11}. Por lo tanto, la cuenta de elementos es 2.Entrada: Q[] = {{1, 101}, {13, 15}}
Salida:
6
0
Enfoque ingenuo: el enfoque más simple para resolver el problema dado es iterar sobre el rango [L, R] para cada consulta e imprimir el recuento de esos números que son palíndromos , y la suma de sus dígitos es un número primo .
Complejidad de tiempo: O(N*(R – L))
Espacio auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar utilizando el principio de inclusión-exclusión y los conceptos de suma de prefijos . Siga los pasos a continuación para resolver el problema dado:
- Inicialice una array arr[] para almacenar el recuento de números hasta cada índice i que son palíndromos y la suma de sus dígitos es un número primo en cada i -ésimo índice .
- Iterar sobre el rango [1, 10 5 ] , y para cada elemento X , si el número X es palindrómico y la suma de los dígitos es primo, entonces actualice arr[i] a 1 . De lo contrario, establezca arr[i] = 0 .
- Encuentre la array de suma de prefijos de la array arr[] .
- Ahora, recorra la array Q[] y para cada consulta {L, R} , imprima el recuento total de los números en el rango [L, R] que son palíndromos y la suma de sus dígitos es un número primo como (arr[ R] – arr[L – 1]) .
A continuación se muestra la implementación del enfoque anterior:
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 not
bool 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 N
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 not
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 numbers
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 numbers
void 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 Code
int 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 approach
class GFG{
static int[] arr = new int[100005];
// Function to check if the number N
// is palindrome or not
static 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 N
static 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 not
static 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 numbers
static 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 numbers
static 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 Code
public 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 approach arr = [0 for i in range(100005)] # Function to check if the number N # is palindrome or not def 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 N def 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 not def 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 numbers def 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 numbers def 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 Code if __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 approach
using System;
class GFG{
static int[] arr = new int[100005];
// Function to check if the number N
// is palindrome or not
static 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 N
static 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 not
static 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 numbers
static 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 numbers
static 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 Code
static 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 approach
let arr = [];
for(let m = 0; m < 100005; m++)
{
arr[m] = 0;
}
// Function to check if the number N
// is palindrome or not
function 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 N
function 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 not
function 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 numbers
function 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 numbers
function 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>
Producción:
2 6
Complejidad Temporal: O(N*log N)
Espacio Auxiliar: O(M), donde M es el elemento máximo entre cada 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