project euler problem 206 https projecteuler netproblem206 find the unique positive integer whose square has the form 1234567890 where each is a single digit instead of computing every single permutation of that number and going through a 109 search space we can narrow it down considerably if the square ends in a 0 then the square root must also end in a 0 thus the last missing digit must be 0 and the square root is a multiple of 10 we can narrow the search space down to the first 8 digits and multiply the result of that by 10 at the end now the last digit is a 9 which can only happen if the square root ends in a 3 or 7 from this point we can try one of two different methods to find the answer 1 start at the lowest possible base number whose square would be in the format and count up the base we would start at is 101010103 whose square is the closest number to 10203040506070809 alternate counting up by 4 and 6 so the last digit of the base is always a 3 or 7 2 start at the highest possible base number whose square would be in the format and count down that base would be 138902663 whose square is the closest number to 1929394959697989 alternate counting down by 6 and 4 so the last digit of the base is always a 3 or 7 the solution does option 2 because the answer happens to be much closer to the starting point determines if num is in the form 123456789 issquareform1 false issquareform112233445566778899 true issquareform123456789012345678 false returns the first integer whose square is of the form 1234567890 determines if num is in the form 1_2_3_4_5_6_7_8_9 is_square_form 1 false is_square_form 112233445566778899 true is_square_form 123456789012345678 false returns the first integer whose square is of the form 1_2_3_4_5_6_7_8_9_0 3 6 10 7 7 4 10 3
def is_square_form(num: int) -> bool:
    
    digit = 9

    while num > 0:
        if num % 10 != digit:
            return False
        num //= 100
        digit -= 1

    return True


def solution() -> int:
    
    num = 138902663

    while not is_square_form(num * num):
        if num % 10 == 3:
            num -= 6  
        else:
            num -= 4  

    return num * 10


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