Dado un número N , la tarea es encontrar la suma de todos los números palindrómicos de N dígitos que son divisibles por 9 y el número no contiene 0.
Nota: La suma puede ser muy grande, toma módulo con 10 9 +7.
Ejemplo:
Entrada: N = 2
Salida: 99
Explicación:
Solo hay un número palindrómico de 2 dígitos divisible por 9 que es 99.
Entrada: N = 3
Salida: 4995
Enfoque ingenuo: la idea es iterar sobre todos los números de N dígitos y verificar si los números son palindrómicos y divisibles por 9 y no contienen cero. En caso afirmativo, la suma de todos los números da el resultado requerido.
Enfoque eficiente: a continuación se presentan algunas observaciones para esta declaración del problema:
- Si N es impar, entonces el número puede tener la forma «ab..x..ba» y si N es par, entonces el número puede ser «ab..xx..ba» , donde ‘a’, ‘b’ y ‘x’ se puede reemplazar por dígitos del 1 al 9.
- Si el número “ab..x..ba” es divisible por 9, (2*(a+b) + x) debe ser divisible por 9 .
- Para cada par posible de (a, b) siempre existe una ‘x’ tal que el número es divisible por 9.
- Luego, el recuento de números palindrómicos de N dígitos que son divisibles por 9 se puede calcular a partir de la siguiente fórmula:
Since we have 9 digits to fill at the position a and b. Therefore, total possible combinations will be: if N is Odd then, count = pow(9, N/2) if N is Even then, count = pow(9, N/2 - 1) as N/2 digits are repeated at the end to get the number palindromic.
Prueba de Unicidad de ‘x’:
- El valor mínimo de a y b es 1, por lo tanto, la suma mínima = 2.
- El valor máximo de a y b es 9, por lo tanto, la suma mínima = 18.
- Como los números son palindrómicos, entonces la suma viene dada por:
sum = 2*(a+b) + x;
- 2*(a+b) será de la forma 2, 4, 6, 8, …, 36. Para hacer la suma divisible por 9 el valor de x puede ser:
sum one of the possible value of x sum + x 2 7 9 4 5 9 6 3 9 8 1 9 . . . . . . . . . 36 9 45
A continuación se muestran los pasos:
- Después de las observaciones anteriores, la suma del dígito de todos los números palindrómicos de N dígitos que es divisible por 9 en cualquier posición k-ésima está dada por:
sum at kth position = 45*(number of combinations)/9
- Repita un ciclo sobre [1, N] y encuentre el número de combinaciones posibles para colocar un dígito en el índice actual.
- Encuentre la suma de todos los dígitos en el dígito actual usando la fórmula mencionada anteriormente.
- La suma de todas las sumas calculadas en cada iteración dado el resultado requerido.
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;
long long int MOD = 1000000007;
// Function to find a^b efficiently
long long int power(long long int a,
long long int b)
{
// Base Case
if (b == 0)
return 1;
// To store the value of a^b
long long int temp = power(a, b / 2);
temp = (temp * temp) % MOD;
// Multiply temp by a until b is not 0
if (b % 2 != 0) {
temp = (temp * a) % MOD;
}
// Return the final ans a^b
return temp;
}
// Function to find sum of all N-digit
// palindromic number divisible by 9
void palindromicSum(int N)
{
long long int sum = 0, res, ways;
// Base Case
if (N == 1) {
cout << "9" << endl;
return;
}
if (N == 2) {
cout << "99" << endl;
return;
}
ways = N / 2;
// If N is even, decrease ways by 1
if (N % 2 == 0)
ways--;
// Find the total number of ways
res = power(9, ways - 1);
// Iterate over [1, N] and find the
// sum at each index
for (int i = 0; i < N; i++) {
sum = sum * 10 + 45 * res;
sum %= MOD;
}
// Print the final Sum
cout << sum << endl;
}
// Driver Code
int main()
{
int N = 3;
palindromicSum(N);
return 0;
}
Java
// Java program for the above approach
class GFG{
static int MOD = 1000000007;
// Function to find a^b efficiently
static int power(int a, int b)
{
// Base Case
if (b == 0)
return 1;
// To store the value of a^b
int temp = power(a, b / 2);
temp = (temp * temp) % MOD;
// Multiply temp by a until b is not 0
if (b % 2 != 0)
{
temp = (temp * a) % MOD;
}
// Return the final ans a^b
return temp;
}
// Function to find sum of all N-digit
// palindromic number divisible by 9
static void palindromicSum(int N)
{
int sum = 0, res, ways;
// Base Case
if (N == 1)
{
System.out.print("9" + "\n");
return;
}
if (N == 2)
{
System.out.print("99" + "\n");
return;
}
ways = N / 2;
// If N is even, decrease ways by 1
if (N % 2 == 0)
ways--;
// Find the total number of ways
res = power(9, ways - 1);
// Iterate over [1, N] and find the
// sum at each index
for (int i = 0; i < N; i++)
{
sum = sum * 10 + 45 * res;
sum %= MOD;
}
// Print the final Sum
System.out.print(sum + "\n");
}
// Driver Code
public static void main(String[] args)
{
int N = 3;
palindromicSum(N);
}
}
// This code is contributed by Amit Katiyar
Python3
# Python 3 program for the above approach
MOD = 1000000007
# Function to find a^b efficiently
def power(a, b):
# Base Case
if (b == 0):
return 1
# To store the value of a^b
temp = power(a, b // 2)
temp = (temp * temp) % MOD
# Multiply temp by a until b is not 0
if (b % 2 != 0):
temp = (temp * a) % MOD
# Return the final ans a^b
return temp
# Function to find sum of all N-digit
# palindromic number divisible by 9
def palindromicSum(N):
sum = 0
# Base Case
if (N == 1):
print("9")
return
if (N == 2):
print("99")
return
ways = N // 2
# If N is even, decrease ways by 1
if (N % 2 == 0):
ways -= 1
# Find the total number of ways
res = power(9, ways - 1)
# Iterate over [1, N] and find the
# sum at each index
for i in range(N):
sum = sum * 10 + 45 * res
sum %= MOD
# Print the final Sum
print(sum)
# Driver Code
if __name__ == "__main__":
N = 3
palindromicSum(N)
# This code is contributed by chitranayal
C#
// C# program for the above approach
using System;
class GFG{
static int MOD = 1000000007;
// Function to find a^b efficiently
static int power(int a, int b)
{
// Base Case
if (b == 0)
return 1;
// To store the value of a^b
int temp = power(a, b / 2);
temp = (temp * temp) % MOD;
// Multiply temp by a until b is not 0
if (b % 2 != 0)
{
temp = (temp * a) % MOD;
}
// Return the readonly ans a^b
return temp;
}
// Function to find sum of all N-digit
// palindromic number divisible by 9
static void palindromicSum(int N)
{
int sum = 0, res, ways;
// Base Case
if (N == 1)
{
Console.Write("9" + "\n");
return;
}
if (N == 2)
{
Console.Write("99" + "\n");
return;
}
ways = N / 2;
// If N is even, decrease ways by 1
if (N % 2 == 0)
ways--;
// Find the total number of ways
res = power(9, ways - 1);
// Iterate over [1, N] and find the
// sum at each index
for(int i = 0; i < N; i++)
{
sum = sum * 10 + 45 * res;
sum %= MOD;
}
// Print the readonly sum
Console.Write(sum + "\n");
}
// Driver Code
public static void Main(String[] args)
{
int N = 3;
palindromicSum(N);
}
}
// This code is contributed by AbhiThakur
Javascript
<script>
// Javascript program for the above approach
let MOD = 1000000007;
// Function to find a^b efficiently
function power(a, b)
{
// Base Case
if (b == 0)
return 1;
// To store the value of a^b
let temp = power(a, b / 2);
temp = (temp * temp) % MOD;
// Multiply temp by a until b is not 0
if (b % 2 != 0)
{
temp = (temp * a) % MOD;
}
// Return the final ans a^b
return temp;
}
// Function to find sum of all N-digit
// palindromic number divisible by 9
function palindromicSum(N)
{
let sum = 0, res, ways;
// Base Case
if (N == 1)
{
document.write("9" + "\n");
return;
}
if (N == 2)
{
document.write("99" + "\n");
return;
}
ways = Math.floor(N / 2);
// If N is even, decrease ways by 1
if (N % 2 == 0)
ways--;
// Find the total number of ways
res = power(9, ways - 1);
// Iterate over [1, N] and find the
// sum at each index
for (let i = 0; i < N; i++)
{
sum = sum * 10 + 45 * res;
sum %= MOD;
}
// Print the final Sum
document.write(sum + "<br/>");
}
// Driver Code
let N = 3;
palindromicSum(N);
</script>
Producción:
4995
Complejidad temporal: O(N), donde N es el número dado.
Publicación traducida automáticamente
Artículo escrito por piyushbhutani y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA