Find the Nth number that contains at least one even digit

user_15518725 0
Viewed 216

I am looking at this challenge:

Find the Nth number that contains at least one even digit.

Example results for values of N:

N result
1 2
2 4
3 6
4 8
5 10
6 12
7 14
8 16
9 18
10 20
11 21
12 22
13 23
14 24
... ...

N is natural number and 0 < N < 1018

The program must return the correct result within 1 second.

Here is my attempt:

N = 14
number = 0

while N > 0:
    number += 1

    if '0' in str(number) or '2' in str(number) or '4' in str(number) or '6' in str(number) or '8' in str(number):
        N -= 1

print(number) // 24

This code is working, but it cannot resolve this task in 1 second if N is 1018 or even 1016. When N is a big integer, the while loop is taking too many iterations...

How can I speed up this program?

algorithm python
1 Answers

You can solve this with recursion.

An important observation is that the count of "good" numbers below a certain limit, i.e. numbers with at least one even digit, is equal to:

  • The number itself (counting all numbers starting from 0)
  • Excluding all numbers that only consist of odd digits
  • Excluding zero

The count of numbers that only consist of odd digits below a power of 10 is:

  • 5 + 5² + 5³ + ... + 5k, where k is that power, which is equal to (5k+1-1)/4-1

And the count of numbers that only consist of odd digits between a power of 10 and twice that power of 10 (so those numbers have a fixed count of digits, always starting with 1), is:

  • 5k

Of course, if the most significant digit is 2 (or another even digit), the count of odd numbers is zero.

So with those ingredients you can build a solution:

def count_even(digit, num_zeroes):
    # The arguments encode a number that only has one non-zero digit, the first:
    # - digit: the most significant digit (1..9)
    # - num_zeroes: the count of trailing zeroes
    # Returns the count of numbers less than this encoded number that have at
    #   least one even digit
    return (10**num_zeroes * digit  # count all numbers 
        # exclude numbers with fewer digits and only odd digits:
        - ((5**(num_zeroes+1)-1)//4-1)   
        # exclude numbers with same digit count and only odd digits, 
        #  but with first digit less than given digit,
        - 5**num_zeroes * (digit//2)
        # ...and exclude 0
        - 1
    )

# The main algorithm
def get_nth_with_even_digit(n):
    # Base cases
    if n < 10: 
        return n * 2  # 2, 4, 6, ..., 18
    if n < 20:
        return 10 + n  # 20 - 29

    # Use recursion to build on previous results:
    num_zeroes = 1
    while True:
        diff = count_even(3, num_zeroes) - count_even(1, num_zeroes)
        num_zeroes += 1
        power = 10**num_zeroes
        limit = 1 + count_even(2, num_zeroes)
        if n < limit:
            return power//5 + get_nth_with_even_digit(n - diff)
        if n < limit + power:
            return n + power//5 + get_nth_with_even_digit(limit - diff) - limit

While testing the code, I used a brute force implementation like your own, and compared the outcome with the outcome from the above function:

# Testing code - will keep running until a difference is found with the brute force method
def brute():
    for i in range(10000000000):
        if any(d in "02468" for d in str(i)):
            yield i

for n, expected in enumerate(brute()):
    got = get_nth_with_even_digit(n)
    assert got == expected, "{}: got {}, expected {}".format(n, got, expected)
    print(n, expected)
user_54598390
Related