Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

project euler
reverse
communitycreator

ProjectEuler 145: How many reversible numbers are below 1 million

Armaan Nougai

Problem statement

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)?

Question analysis

Here, the problem has assigned a new definition to the term reversible. We must understand how it works.

widget

Approach 1

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.

Optimizations
  1. There are no reversible numbers between 10^8 and 10^9.

  2. 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.

widget

Approach 2

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.


Condition 1: digit numbers ()
no possible solution

Condition 2: digit numbers (a,b)
(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

Condition 3: digit numbers (a,b,c)
(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

Condition 4: digit numbers (a,b,c,d)
(a + d) % 2 = 1
 
(a + d) < 10

Total numbers = 20*30 = 600
%0 node_1630171716434 a+d node_1 b+c node_2 c+b node_3 d+a

Condition 5: digit numbers (a,b,c,d,e)
(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

Condition 6: digit numbers (a,b,c,d,e,f)
(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

Condition 7: digit numbers (a,b,c,d,e,f,g)
(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

Condition 8: digit numbers (a,b,c,d,e,f,g,h)
(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

Condition 9: digit numbers (a,b,c,d,e,f,g,h,i)
// 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

Summary

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

Code

"""
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

project euler
reverse
communitycreator
RELATED COURSES

View all Courses

Keep Exploring