# The major optimization is to do arithmetic in base 10 in the main loop, avoiding division and modulo
def problem206():
    """
    Find the unique positive integer whose square has the form
       1_2_3_4_5_6_7_8_9_0,
       where each “_” is a single digit.
    """
    # Initialize
    n = 1000000000  # The pattern is greater than 10^18, so start searching at 10^9

    ndigits = [0] * 10  # In base 10, little-endian
    temp = n
    for i in range(len(ndigits)):
        ndigits[i] = temp % 10
        temp //= 10

    n2digits = [0] * 19  # Based on length of pattern
    temp = n * n
    for i in range(len(n2digits)):
        n2digits[i] = temp % 10
        temp //= 10

    # Increment and search
    while not is_concealed_square(n2digits):
        # Add 20n + 100 so that n2digits = (n + 10)^2
        add_20n(ndigits, n2digits)
        add_10pow(n2digits, 2)

        # Since n^2 ends with 0, n must end with 0
        n += 10
        add_10pow(ndigits, 1)
    # Now n2digits = n^2
    return n


def is_concealed_square(n):
    for i in range(1, 10):  # Scan for 1 to 9
        if n[20 - i * 2] != i:
            return False
    return n[0] == 0  # Special case for 0


def add_10pow(n, i):
    while n[i] == 9:
        n[i] = 0
        i += 1
    n[i] += 1


def add_20n(n, n2):
    carry = 0
    i = 0
    while i < len(n):
        sum = n[i] * 2 + n2[i + 1] + carry
        n2[i + 1] = sum % 10
        carry = sum // 10
        i += 1
    i += 1
    while carry > 0:
        sum = n2[i] + carry
        n2[i] = sum % 10
        carry = sum // 10
        i += 1


if __name__ == "__main__":
    print(problem206())
