An integer is called reversible
if n + reverse(n)
consists only of odd digits. There are 120 such numbers less than 1000.
How many reversible numbers are there that are less than 10^9 (one-billion)?
Here, the problem has assigned a new definition to the term reversible. We must understand how it works.
One neophyte way to approach this problem is by simply checking each number to see if it satisfies the condition (i.e., n+rev(n) should contain only odd digits), until one-billion.
There are no reversible numbers between 10^8 and 10^9.
if n
is reversible, then n
's literal reverse is also reversible. We will avoid checking both of them by just checking one and then adding 2 instead of 1 in the result.
This solution approach is brain-racking, but this is only because it is long. The upside is that its implementation is a whole lot of small and fast.
Here, we will find out conditions for reversible numbers for the different numbers of digits.
Exactly one of the first and the last numbers must be odd.
no possible solution
(a + b) % 2 = 1
a + b < 10, // so that the last digit doesn't pass on its carryover to the first digit, making it even.
Total numbers = 20
(a + c) % 2 = 1
a + c > 10. // since b will be added to itself therefore it will need a carryover from the last digit.
Total numbers = 5*20 = 100
(a + d) % 2 = 1
(a + d) < 10
Total numbers = 20*30 = 600
(d + b) > 10 //since c will be added to itself therefore it will need a carryover from the 4th digit but this will lead the 2nd digit pass to carry over to the 1st digit making it even.
Thus, no possible solution
(f + a) % 2 = 1
(b + e) < 10 // otherwise carryover from 2nd digit will make 1st digit even.
(c + d) < 10 // otherwise carryover from 4th digit will make 3rd digit even.
Total numbers = 20 x 30 x 30 = 18000
(a + g) % 2 = 1
// since d will be added to itself, thus need a carryover from the 5th digit.
// Hence, (e + c) > 10
// since (e + c) > 10, 3rd digit will pass carryover to 2nd digit , that means (b + f) % 2 = 0
// Now, the 6th digit is even, to make it odd, 7th digit must be (a + g) > 10 also
Total numbers = 50,000
(a + h) % 2 = 1
(g + b) < 10 // otherwise it will make the first digit even.
(f + c) < 10 // otherwise it will make the second digit even.
(e + d) < 10 // otherwise it will make the third digit even.
Total numbers = 20 x 30 x 30 x 30 = 540000
// e will be added to itself, but if we keep on going setting up favorable conditions, eventually the first digit will get even.
// So, no possible solutions
For this problem, we can get answers just by adding possible solutions for digits (1-9).
But we can also see some pattern here. For example:
// if n is even, then possible reversible numbers of n digits = 20 * 30 ^ (n/2 - 1)
// now if n % 4 = 1, then possible reversible numbers of n digits = 20 x 20 * (20 * 25) ^ (n/4 - 1)
// and for n % 4 = 3, then possible reversible numbers of n digits = 0
""" Coded by - Armaan Nougai """ def rev(b): t_rev = 0 while b > 9: t_rev = t_rev * 10 + b % 10 b //= 10 return t_rev * 10 + b def oddcheck(v): while v > 0: value = v % 10 if value % 2 == 0: return False v //= 10 return True cnt_rev = 0 for j in range(11, 100000000, 2): if oddcheck(j + rev(j)): cnt_rev += 2 print(cnt_rev)
RELATED TAGS
CONTRIBUTOR
View all Courses