CODEWITHSUNDEEP
python
Dimitri Sifoua
Dimitri Sifoua

Reputation: 499

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

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:

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?

Upvotes: 10

Views: 10517

Answers (3)

wyz23x2
wyz23x2

Reputation: 306

6 seconds? That seems really hard in Python, usually slow compared to C, Java etc. Even though I haven't figured out a way that passes the test, there are a few places you can improve:

1. is_lucky

nbr can be just converted to str, no need to unpack into list. str supports in. Use the fact that in mathematical calcs, True==1, False==0.
E.g. A is '6' in nbr, B is '8' in nbr:
Both are true, A+B=2
One is true, A+B=1
Both are false, A+B=0
So we can just check if A+B == 1.

Before:

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

After:

def is_lucky(nbr):
    nbr = str(nbr)
    return ('6' in nbr) + ('8' in nbr) == 1

2. The loop

If the number now has checked False, we can improve it.
If the final digit is less than 5, increment 6-n%10.
For example, 311 isn't a lucky number. So of course 312~315 aren't, too, so just add directly to 316 by 6-1=5.
Why not <6? 5 adds 1 no matter what, so we don't need it :]

Before:

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

After:

number, s = L, 0
while n <= H:
    x = is_lucky(number)
    n_lucky_number += x
    m = number % 10
    if not x and m < 5:
        number += 6-m
    else:
        number += 1
print(n_lucky_number)

Upvotes: -2

Tranbi
Tranbi

Reputation: 12731

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)

Upvotes: 2

sulav shrestha
sulav shrestha

Reputation: 41

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

Upvotes: 3

Related Questions