"""
== Keith Number (Repfigit Number) ==
A Keith number (also known as a repfigit number, short for "repetitive
Fibonacci-like digit") is a natural number n with d >= 2 decimal digits
such that when a sequence is formed starting with the d digits of n and each
subsequent term is the sum of the preceding d terms, the number n itself
appears in the sequence.

For example, 197 is a 3-digit number (d = 3):
    Initial terms: 1, 9, 7
    Next term: 1 + 9 + 7 = 17
    Next term: 9 + 7 + 17 = 33
    Next term: 7 + 17 + 33 = 57
    Next term: 17 + 33 + 57 = 107
    Next term: 33 + 57 + 107 = 197 (Matches 197! So 197 is a Keith number).

The first few Keith numbers are:
14, 19, 28, 47, 61, 75, 197, 742, 1104, 1537, 2208, 2580, 3684, 4788, 7385...

References:
- https://en.wikipedia.org/wiki/Keith_number
- https://oeis.org/A007629
"""

from collections import deque


def is_keith_number(number: int) -> bool:
    """
    Check if a given integer is a Keith number.

    A Keith number is an integer greater than or equal to 10 that appears
    in the Fibonacci-like sequence generated by its digits. Single-digit
    numbers are excluded by mathematical convention.

    Complexity Analysis:
        - Time Complexity: O(d * k) where d is the number of digits of number
          and k is the number of terms until the sequence reaches or exceeds
          the number. Since the terms grow exponentially, k = O(log(number)).
        - Space Complexity: O(d) auxiliary space to store the previous d terms.

    Args:
        number: The integer to test.

    Returns:
        True if number is a Keith number, False otherwise.

    Raises:
        TypeError: If number is not an integer.

    Examples:
        Known 2-digit Keith numbers:
        >>> is_keith_number(14)
        True
        >>> is_keith_number(19)
        True
        >>> is_keith_number(28)
        True
        >>> is_keith_number(47)
        True
        >>> is_keith_number(61)
        True
        >>> is_keith_number(75)
        True

        Known 3-digit and 4-digit Keith numbers:
        >>> is_keith_number(197)
        True
        >>> is_keith_number(742)
        True
        >>> is_keith_number(1104)
        True
        >>> is_keith_number(1537)
        True

        Non-Keith numbers:
        >>> is_keith_number(10)
        False
        >>> is_keith_number(12)
        False
        >>> is_keith_number(25)
        False
        >>> is_keith_number(100)
        False

        Edge cases (single-digit and non-positive integers):
        >>> is_keith_number(9)
        False
        >>> is_keith_number(1)
        False
        >>> is_keith_number(0)
        False
        >>> is_keith_number(-14)
        False

        Type validation:
        >>> is_keith_number(14.0)
        Traceback (most recent call last):
            ...
        TypeError: number must be an integer
        >>> is_keith_number("14")
        Traceback (most recent call last):
            ...
        TypeError: number must be an integer
        >>> is_keith_number(True)
        Traceback (most recent call last):
            ...
        TypeError: number must be an integer
        >>> is_keith_number(None)
        Traceback (most recent call last):
            ...
        TypeError: number must be an integer
    """
    if not isinstance(number, int) or isinstance(number, bool):
        raise TypeError("number must be an integer")

    if number < 10:
        return False

    digits = [int(digit) for digit in str(number)]
    window = deque(digits)
    current_sum = sum(digits)

    while current_sum < number:
        oldest = window.popleft()
        window.append(current_sum)
        # Update rolling sum in O(1)
        current_sum = 2 * current_sum - oldest

    return current_sum == number


def find_keith_numbers(limit: int) -> list[int]:
    """
    Find and return all Keith numbers up to a specified limit.

    Complexity Analysis:
        - Time Complexity: O(limit * log(limit))
        - Space Complexity: O(k) where k is the number of Keith numbers found.

    Args:
        limit: The upper bound (inclusive) up to which to search for Keith numbers.

    Returns:
        A list of Keith numbers less than or equal to limit.

    Raises:
        TypeError: If limit is not an integer.
        ValueError: If limit is less than 10.

    Examples:
        >>> find_keith_numbers(100)
        [14, 19, 28, 47, 61, 75]
        >>> find_keith_numbers(200)
        [14, 19, 28, 47, 61, 75, 197]
        >>> find_keith_numbers(10)
        []

        Type and value errors:
        >>> find_keith_numbers(9)
        Traceback (most recent call last):
            ...
        ValueError: limit must be an integer greater than or equal to 10
        >>> find_keith_numbers(10.5)
        Traceback (most recent call last):
            ...
        TypeError: limit must be an integer
        >>> find_keith_numbers(False)
        Traceback (most recent call last):
            ...
        TypeError: limit must be an integer
    """
    if not isinstance(limit, int) or isinstance(limit, bool):
        raise TypeError("limit must be an integer")
    if limit < 10:
        raise ValueError("limit must be an integer greater than or equal to 10")

    return [num for num in range(10, limit + 1) if is_keith_number(num)]


if __name__ == "__main__":
    import doctest

    doctest.testmod()