Se dice que un número es reversible si la suma del número y su reverso tiene solo dígitos impares. El problema es saber si un número es reversible o no.
Ejemplos:
Input: 36 Output: Reversible number as 36 + 63 = 99 has only odd digits. Input: 409 Output: Reversible number as 409 + 904 = 1313 has only odd digits. Input: 35 Output: Not Reversible number as 35 + 53 = 88 has only odd digits
método ingenuo
Calcula el reverso de cada número y súmalo al número. Si la resultante es reversible incrementa el valor de cuenta. Calcula esto para cada número del 1 al n.
Complejidad de tiempo: O (10 ^ n) ya que debería calcular el reverso de cada número.
Método avanzado
- Número de 1 dígito: cualquier número de un dígito se sumará a sí mismo, que siempre será un número par, y por lo tanto no hay soluciones.
- Número de 2 dígitos: Ambos dígitos deben ser impares.
- Si a+b > 10, entonces tenemos un remanente y, por lo tanto, el primer dígito del resultado tendrá una paridad diferente a la del segundo dígito.
- Entonces, las soluciones solo se pueden formar donde a+b < 10 y a + b es impar. Entonces, un total de 20 números de este tipo son posibles.
- Número de 3 dígitos:
- El dígito del medio debe sumarse a sí mismo. Eso significa que el tercer dígito debe tener un remanente y ser impar.
- Dado que el tercer dígito es impar, el primer dígito también es impar si el segundo dígito no tiene un remanente, lo que sucede cuando el segundo dígito es menor que 5, lo que nos da 20 opciones para el primer/tercer dígito y 5 opciones para el medio. Por lo tanto, un total de 100 pares.
- Número de 4 dígitos: hay dos pares, digamos el par interno y externo.
- Si el par interno tiene remanente, entonces el par externo también debe tener remanente.
- De lo contrario, los dos pares internos tendrán una paridad diferente.
- Si el par interior tiene traspaso, entonces el par exterior tendrá una paridad diferente, ya que el primer dígito terminará con un traspaso que el último dígito no obtendría.
- Por lo tanto, tenemos soluciones solo cuando ninguno de los pares tiene transferencia.
- En total: para el par externo, esto nos da las 20 opciones que hemos visto en el caso de dos dígitos. Y nos da 30 casos para el par interior ya que también pueden contener un cero.
O en total obtenemos 20*30 = 600 soluciones.
- Número de 5, 9, 13.. dígitos: No hay solución como número de 1 dígito.
- Número de 6, 8, 10… dígitos: Igual que un número de 2 dígitos, es decir, si n = 2*k entonces la solución total = 20*30^(k-1).
- 7, 11, 15.. número de dígitos: Igual que el número de 3 dígitos, es decir, si n = 4k + 3, entonces la solución total = 100*500^(k).
Generalizando la solución:
- Todos los dígitos pares (2, 4, 6, 8…) tienen la misma fórmula, por lo que podemos generalizar
que para algún número entero k tal que n = 2k tenemos 20*30^(k-1) soluciones
que representan el par exterior junto con todos los pares internos. - Para n (3, 7, 11..) de la forma 4k + 3 (k es un número entero), tenemos que el dígito medio y
el par exterior nos da 5 y 20 opciones, como en el caso de un número de 3 dígitos.
Entonces tenemos conjuntos de pares internos que nos dan 20 y 25 soluciones.
Eso significa que podemos generalizarlo a 20*5*(20*25)^(k) = 100*500^(k). - Para n de forma 4k+ 1 lo que significa 1, 5, 9… ninguno de estos tiene solución.
Programa para comprobar si un número es reversible o no
C++
// C++ program to check if a given
// number is reversible or not
#include <iostream>
#include <cmath>
using namespace std;
// Function to check reversible number
void checkReversible (int n)
{
int rev = 0, rem;
// Calculate reverse of n
int flag = n;
while (flag)
{
rem = flag % 10;
rev *= 10;
rev += rem;
flag /= 10;
}
// Calculate sum of number
// and its reverse
int sum = rev + n;
// Check for reverse number
// reach digit must be odd
while (sum && (rem % 2 != 0))
{
rem = sum % 10;
sum /= 10;
}
if (sum == 0)
cout << "Reversible Number";
else
cout << "Non-Reversible Number";
}
// Driver function
int main()
{
int n = 36;
checkReversible(n);
return 0;
}
Java
// Java program to check if a given
// number is reversible or not
import java.io.*;
class GFG {
// Function to check reversible number
static void checkReversible (int n)
{
int rev = 0, rem = 0;
// Calculate reverse of n
int flag = n;
while (flag>0)
{
rem = flag % 10;
rev *= 10;
rev += rem;
flag /= 10;
}
// Calculate sum of number
// and its reverse
int sum = rev + n;
// Check for reverse number
// reach digit must be odd
while (sum > 0 && (rem % 2 != 0))
{
rem = sum % 10;
sum /= 10;
}
if (sum == 0)
System.out.println("Reversible Number");
else
System.out.println("Non-Reversible Number");
}
// Driver function
public static void main (String[] args)
{
int n = 36;
checkReversible(n);
}
}
// This code is contributed by vt_m.
Python3
# Python3 program to check if a given
# number is reversible or not
# Function to check reversible number
def checkReversible (n):
rev = 0
# Calculate reverse of n
flag = n
while (flag != 0):
rem = flag % 10
rev *= 10
rev += rem
flag //= 10
# Calculate sum of number
# and its reverse
sum = rev + n
# Check for reverse number
# reach digit must be odd
while (sum and ((rem % 2) != 0)):
rem = sum % 10
sum //= 10
if (sum == 0):
print("Reversible Number")
else:
print("Non-Reversible Number")
# Driver Code
n = 36
checkReversible(n)
# This code is contributed by sanjoy_62
C#
// C# program to check if a given
// number is reversible or not
using System;
class GFG {
// Function to check reversible number
static void checkReversible (int n)
{
int rev = 0, rem = 0;
// Calculate reverse of n
int flag = n;
while (flag > 0)
{
rem = flag % 10;
rev *= 10;
rev += rem;
flag /= 10;
}
// Calculate sum of number
// and its reverse
int sum = rev + n;
// Check for reverse number
// reach digit must be odd
while (sum > 0 && (rem % 2 != 0))
{
rem = sum % 10;
sum /= 10;
}
if (sum == 0)
Console.WriteLine("Reversible Number");
else
Console.WriteLine("Non-Reversible Number");
}
// Driver function
public static void Main ()
{
int n = 36;
checkReversible(n);
}
}
// This code is contributed by vt_m.
Javascript
// JavaScript program to check if a given
// number is reversible or not
// Function to check reversible number
function checkReversible (n)
{
var rev = 0;
// Calculate reverse of n
var flag = n;
while (flag != 0)
{
rem = flag % 10
rev *= 10
rev += rem
flag = Math.floor(flag / 10);
}
// Calculate sum of number
// and its reverse
var sum = rev + n;
// Check for reverse number
// reach digit must be odd
while (sum && ((rem % 2) != 0))
{
rem = sum % 10
sum = Math.floor(sum / 10);
}
if (sum == 0)
console.log("Reversible Number")
else
console.log("Non-Reversible Number")
}
// Driver Code
let n = 36
checkReversible(n);
// This code is contributed by phasing17
Producción:
Reversible Number
Complejidad del tiempo : O (log N) donde N no es ningún dígito del número n
Programa Para contar números reversibles totales hasta n
C++
// C++ program to find the count of
// reversible numbers upto a given number n
#include <iostream>
#include <cmath>
using namespace std;
// Function to calculate the count of reversible number
void countReversible (int n)
{
int count = 0;
// Calculate counts of
// reversible number of 1 to n-digits
for ( int i = 1; i <= n; i++)
{
// All four possible cases and their formula
switch (i % 4)
{
// for i of form 2k
case 0:
case 2:
count += 20 * pow( 30, ( i / 2 - 1));
break;
// for i of form 4k + 3
case 3:
count += 100 * pow ( 500, i / 4 );
break;
// for i of form 4k + 1 no solution
case 1:
break;
}
}
cout << count;
}
// Driver function
int main()
{
// count up-to 9 digit numbers (1 billion)
int n = 9;
countReversible(n);
return 0;
}
Java
// Java program to find the count of
// reversible numbers upto a given number n
import java.io.*;
class GFG {
// Function to calculate the count
// of reversible number
static void countReversible (int n)
{
int count = 0;
// Calculate counts of
// reversible number of 1 to n-digits
for ( int i = 1; i <= n; i++)
{
// All four possible cases
// and their formula
switch (i % 4)
{
// for i of form 2k
case 0:
case 2:
count += 20 * Math.pow( 30, ( i / 2 - 1));
break;
// for i of form 4k + 3
case 3:
count += 100 * Math.pow ( 500, i / 4 );
break;
// for i of form 4k + 1 no solution
case 1:
break;
}
}
System.out.println(count);
}
// Driver function
public static void main (String[] args)
{
// count up-to 9 digit numbers (1 billion)
int n = 9;
countReversible(n);
}
}
// This code is contributed by vt_m.
C#
// C# program to find the count of
// reversible numbers upto a given number n
using System;
class GFG {
// Function to calculate the
// count of reversible number
static void countReversible (int n)
{
int count = 0;
// Calculate counts of
// reversible number of 1 to n-digits
for ( int i = 1; i <= n; i++)
{
// All four possible cases
// and their formula
switch (i % 4)
{
// for i of form 2k
case 0:
case 2:
count += 20 * (int)Math.Pow( 30, ( i / 2 - 1));
break;
// for i of form 4k + 3
case 3:
count += 100 * (int)Math.Pow ( 500, i / 4 );
break;
// for i of form 4k + 1 no solution
case 1:
break;
}
}
Console.WriteLine(count);
}
// Driver function
public static void Main ()
{
// count up-to 9 digit numbers (1 billion)
int n = 9;
countReversible(n);
}
}
// This code is contributed by vt_m.
Javascript
// JavaScript program to find the count of
// reversible numbers upto a given number n
// Function to calculate the count of reversible number
function countReversible (n)
{
let count = 0;
// Calculate counts of
// reversible number of 1 to n-digits
for (let i = 1; i <= n; i++)
{
// All four possible cases and their formula
switch (i % 4)
{
// for i of form 2k
case 0:
case 2:
count += 20 * Math.pow( 30, Math.floor( i / 2 - 1));
break;
// for i of form 4k + 3
case 3:
count += 100 * Math.pow ( 500, Math.floor(i / 4) );
break;
// for i of form 4k + 1 no solution
case 1:
break;
}
}
console.log (count);
}
// Driver function
// count up-to 9 digit numbers (1 billion)
let n = 9;
countReversible(n);
// This code is contributed by phasing17
Producción:
608720
Complejidad de tiempo : O(nlogn)
Espacio auxiliar : O(1)
Referencia: Proyecto Euler 145: ¿Cuántos números reversibles hay debajo de mil millones?
Este artículo es una contribución de Shivam Pradhan (anuj_charm) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA