project euler problem 104 https projecteuler netproblem104 the fibonacci sequence is defined by the recurrence relation fn fn1 fn2 where f1 1 and f2 1 it turns out that f541 which contains 113 digits is the first fibonacci number for which the last nine digits are 19 pandigital contain all the digits 1 to 9 but not necessarily in order and f2749 which contains 575 digits is the first fibonacci number for which the first nine digits are 19 pandigital given that fk is the first fibonacci number for which the first nine digits and the last nine digits are 19 pandigital find k takes a number and checks if it is pandigital both from start and end check123456789987654321 true check120000987654321 false check1234567895765677987654321 true mark last 9 numbers flag check last 9 numbers for pandigitality mark first 9 numbers check first 9 numbers for pandigitality takes a number and checks if it is pandigital from end check1123456789987654321 true check1120000987654321 true check112345678957656779870004321 false mark last 9 numbers flag check last 9 numbers for pandigitality outputs the answer is the least fibonacci number pandigital from both sides solution 329468 temporary fibonacci numbers temporary fibonacci numbers mod 1e9 mod m1e9 done for fast optimisation perform check only if in tocheck type ignore takes a number and checks if it is pandigital both from start and end check 123456789987654321 true check 120000987654321 false check 1234567895765677987654321 true mark last 9 numbers flag check last 9 numbers for pandigitality mark first 9 numbers check first 9 numbers for pandigitality takes a number and checks if it is pandigital from end check1 123456789987654321 true check1 120000987654321 true check1 12345678957656779870004321 false mark last 9 numbers flag check last 9 numbers for pandigitality outputs the answer is the least fibonacci number pandigital from both sides solution 329468 temporary fibonacci numbers temporary fibonacci numbers mod 1e9 mod m 1e9 done for fast optimisation perform check only if in tocheck first 2 already done
import sys

sys.set_int_max_str_digits(0)  


def check(number: int) -> bool:
    

    check_last = [0] * 11
    check_front = [0] * 11

    
    for _ in range(9):
        check_last[int(number % 10)] = 1
        number = number // 10
    
    f = True

    

    for x in range(9):
        if not check_last[x + 1]:
            f = False
    if not f:
        return f

    
    number = int(str(number)[:9])

    for _ in range(9):
        check_front[int(number % 10)] = 1
        number = number // 10

    

    for x in range(9):
        if not check_front[x + 1]:
            f = False
    return f


def check1(number: int) -> bool:
    

    check_last = [0] * 11

    
    for _ in range(9):
        check_last[int(number % 10)] = 1
        number = number // 10
    
    f = True

    

    for x in range(9):
        if not check_last[x + 1]:
            f = False
    return f


def solution() -> int:
    

    a = 1
    b = 1
    c = 2
    

    a1 = 1
    b1 = 1
    c1 = 2
    

    
    tocheck = [0] * 1000000
    m = 1000000000

    for x in range(1000000):
        c1 = (a1 + b1) % m
        a1 = b1 % m
        b1 = c1 % m
        if check1(b1):
            tocheck[x + 3] = 1

    for x in range(1000000):
        c = a + b
        a = b
        b = c
        
        if tocheck[x + 3] and check(b):
            return x + 3  
    return -1


if __name__ == "__main__":
    print(f"{solution() = }")