Beautiful Numbers

Question

A sequence of numbers is called cute if all the numbers in the sequence are made of only two digits, 8 and 9. Example of a cute sequence is: 8, 9, 88, 89, 98, 99…. and so on. A number is called beautiful if it is divisible by any number which is part of the cute sequence. For example: 8 (divisible by 8), 9(divisible by 9), 889 (divisible by 889), 10668 (divisible by 889) are beautiful numbers. Given a number, n, write a code to print “beautiful” (without quotes) if it is divisible by any number that contains only 8 or 9 or both and print -1 otherwise.

This is the python code which i tried:

I used a for loop from 8 to n/2 and i used regex to check if the number contains only 8 and 9. This code is working fine for smaller numbers, for larger numbers it is giving Time limit exceeded! Is there any efficient solution for this question ?

import re
n=int(input())
l="^[8-9]+$"
x=0
if re.match(l,str(n)):
    print("beautiful")
else:
    for i in range(8,int(n/2+1),1):
        if re.match(l,str(i)) and n%i==0:
            print("beautiful")
            x=1
            break
    if x==0:
        print(-1)

Answer 1

n = int(input("enter the number "))

s = str(n)
print(len(s)) 
k = [] a = [8,9] 
flag = 0 

#generate cute sequence numbers by appending 8 and 9 to the already generated numbers

while True:

x = (a[0]*10) + 8
a.append(x)
y = (a[0]*10) + 9
a.append(y)

#check whether the generated number divides the given number

if ((n%x==0) or (n%y==0)):
    flag = 1
    print("beatiful")
    break

if (len(str(y))>len(s)):
    break
k.append(a[0])
a.pop(0) 

print(k)

if (flag==0):

  print("-1") 

Answer 2

There is a function that generates all cute number with specified maximum length:

from collections import deque


elements = ["8", "9"]


def all_cute_numbers(max_len):
    prefixes = deque(elements)
    while prefixes:
        p = prefixes.popleft()
        yield p
        if len(p) < max_len:
            for el in elements:
                prefixes.append(p + el)


numbers = all_cute_numbers(3)
print(list(numbers))

You can loop over it and check that some of number divide your input n