How to count the number of lucky numbers between L and H inclusive?

Question

I've completed a codingame assessment but i was not able to pass all tests on one challenge about lucky numbers. I need some help.

Definition: a lucky number is a number that contains either 6s or 8s in its digits but not both. For example 16, 38, 666 are lucky numbers. 234, 687 are not.

Task: Print the number of lucky numbers between L and H inclusive.

Constraints:

• L < H

• Memory: 512MB

• Time: 6 seconds

Here's what I did (I chose Python as programming language)

def is_lucky(nbr):
    nbr = [*str(nbr)]
    if '6' in nbr and '8' in nbr:
        return False
    if '6' in nbr or '8' in nbr:
        return True
    return False

n_lucky_number = 0
for number in range(L, H + 1):
    n_lucky_number += is_lucky(number)
print(n_lucky_number)

I failed the tests where L and H are big (or the gap between) due to timeout.

L, H = 1, 1000000000000000000

L, H = 92871036442, 3363728910382456

Could someone help me to optimize my code?

Answer 1

def coo(a):
    b=str(a)
    l=len(b)
    c=[]
    count=0
    for i,j in enumerate(b):
        d=l-i-1
        for k in range(int(j)):
            if k==6 or k==8:
                if k==6 and "8" not in c:
                    count=count+9**d
                elif k==8 and "6" not in c:
                    count=count+9**d    
            elif "6" not in c and "8" not in c:
                count=count+2*((9**d)-(8**d))
            elif "6" in c or "8" in c:
                count=count+9**d 
        
        c.append(j)        
        if "6" in c and "8" in c:
            break
    return(int(count))
L=21345323634
H=8392440035734    
print(coo(H+1)-coo(L))

Answer 2

It's an interesting problem and @sulav shrestha has already delivered a working algorithm. Unfortunately his answer lacks some explanation and the code itself can be cleaner.

As others have pointed out, you have to come up with a formula in order to perform with big numbers.

@user3386109 rightfully pointed out that lucky(L,H) = lucky(0,H) - lucky(0,L-1). From there let's see how many lucky numbers there are between 0 and any given number.
In a decimal base, any number can be written like a sum of power of ten:

12345 = 1e4 + 2e3 + 3e2 + 4e1 + 5e0

So let's calculate the number of lucky numbers between 0 and 10^n. It comes down to count the possible combinations of n-digits numbers with either:

• no 8 and at least one 6
• no 6 and at least one 8

The number of combination with no 8 is 9^n (you get to choose among 9 possibilities for each of the n digits). Then you remove all combinations NOT containing any 6: 8^n.

So the number of lucky numbers between 0 and 10^n is 2*(9^n-8^n).

From there you can iterate over your digits from left to right and count:

import time
def magic_numbers_until(num):
    num_str=str(num)
    str_len=len(num_str)
    c=[]
    count=0
    for i,digit in enumerate(num_str):          # we're going from left to right in num
        power_ten=str_len-i-1
        for k in range(int(digit)):             # summing all magic numbers for this power of ten
            if (k==6 or k==8                    # if 6 (resp. 8) was already seen,
                or "6" in c or "8" in c):       # you just calculate the combinations without 8 (resp. 6)
                count=count+9**power_ten 
            else:                               # the case described in my answer
                count=count+2*(9**power_ten-8**power_ten)
        
        c.append(digit)        
        if "6" in c and "8" in c:               # if 6 and 8 are in num, all remaining combinations will be non-magic
            break
    return(int(count))
    
L=1
H=1000000000000000000
t0 = time.time()  
print(magic_numbers_until(H+1)-magic_numbers_until(L))
print(time.time()-t0)