Converting to base-k from base-10 and vice versa

from base-10 to base-k

def int_to_base_k_for_small_bases(n: int, k: int) -> str:
    """
    Converts an integer n (base 10) to a string representation in base k.
    This simplified version only works correctly for bases k <= 10.
    """
    if k < 2 or k > 10: # Enforce the constraint
        raise ValueError("This function is for bases 2-10 only.")
    if n == 0:
        return "0"

    digits = []
    while n > 0:
        remainder = n % k
        digits.append(str(remainder)) # Directly convert integer to string
        n //= k
    return "".join(digits[::-1])

# Example
print(f"13 (base 10) to base 2: {int_to_base_k_for_small_bases(13, 2)}") # Works fine
# print(f"255 (base 10) to base 16: {int_to_base_k_for_small_bases(255, 16)}") # Will raise ValueError

complexity

Base Conversion: O(log_k(M))

Converting number M to base-k takes O(log_k(M)) operations
For each palindrome of value M, we do M % k, M // k repeatedly

if it is bigger than base 10

Define a digit_map: This is a string or list that maps integer values (0-1, 0-9, 0-15, etc.) to their corresponding character representations in the target base. For bases up to 36 (using 0-9 and A-Z), it would be "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ".

def int_to_base_k(n: int, k: int) -> str:
    """
    Converts an integer n (base 10) to a string representation in base k.
    This version correctly handles bases k > 10 by using letters for digits beyond 9.

    Args:
        n: The integer to convert (must be non-negative).
        k: The target base (must be an integer >= 2). Typically up to 36 (0-9, A-Z).

    Returns:
        A string representing the number in base k.
        Returns "0" if n is 0.
        Raises ValueError if k is less than 2 or if k is too large for the digit_map.
    """
    if k < 2:
        raise ValueError("Base k must be an integer greater than or equal to 2.")
    if n == 0:
        return "0"

    digits = []
    # This string contains all possible symbols for digits up to base 36
    # (0-9 for values 0-9, A-Z for values 10-35)
    digit_map = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"

    if k > len(digit_map):
        raise ValueError(f"Base k={k} is too large for the current digit map. Max supported base is {len(digit_map)}.")

    while n > 0:
        remainder = n % k
        # Use the remainder as an index into the digit_map to get the correct character symbol
        digits.append(digit_map[remainder])
        n //= k

    # The digits were collected in reverse order, so join and reverse
    return "".join(digits[::-1])

vice versa

def base_k_to_int(s_num: str, k: int) -> int:
    """
    Converts a string representation of a number in base k to an integer (base 10).

    Args:
        s_num: The string representing the number in base k.
               Can contain digits '0'-'9' and letters 'A'-'F' (or beyond for higher bases).
        k: The base of the input number (must be an integer >= 2).

    Returns:
        The integer (base 10) value of the number.
        Raises ValueError if k is less than 2 or if any digit is invalid for the given base.
    """
    if k < 2:
        raise ValueError("Base k must be an integer greater than or equal to 2.")

    decimal_value = 0
    power = 1 # Represents k^0, then k^1, k^2, etc.

    # Map characters to their integer values (0-9, A=10, B=11, ...)
    # This is the reverse of the digit_map from the previous function
    digit_value_map = {}
    for i in range(10):
        digit_value_map[str(i)] = i
    for i in range(ord('A'), ord('Z') + 1):
        digit_value_map[chr(i)] = i - ord('A') + 10
    
    # Iterate through the digits from right to left
    for char_digit in reversed(s_num):
        if char_digit.upper() not in digit_value_map:
            raise ValueError(f"Invalid digit '{char_digit}' for base {k}.")
        
        digit_int_value = digit_value_map[char_digit.upper()]
        
        if digit_int_value >= k:
            raise ValueError(f"Digit '{char_digit}' is too large for base {k}.")
            
        decimal_value += digit_int_value * power
        power *= k
        
    return decimal_value