1. Hexadecimal and Hexatrigesimal Conversion (LeetCode)
Model answer
The task
The title suggests representing an integer in hexadecimal (base 16) and hexatrigesimal (base 36). The precise input/output contract is unclear, so the solution below provides a generic conversion utility; it uses lowercase digits and a leading minus sign for negative values.
Key idea
Repeatedly divide the number by the target base. The remainders give the digits from right to left, so reverse them at the end. Handle zero separately because it produces no remainders.
Approach
- Define the digit symbols
0through9, thenathroughz. - For each requested base, return
"0"if the value is zero. - Record the sign and repeatedly collect remainders from the absolute value.
- Reverse the collected digits and prepend the sign when needed.
- Convert using bases 16 and 36.
def to_base(n: int, base: int) -> str:
"""Convert an integer to a base from 2 through 36."""
if not 2 <= base <= 36:
raise ValueError("base must be between 2 and 36")
digits = "0123456789abcdefghijklmnopqrstuvwxyz"
if n == 0:
return "0"
sign = "-" if n < 0 else ""
value = abs(n)
result = []
while value > 0:
value, remainder = divmod(value, base)
result.append(digits[remainder])
return sign + "".join(reversed(result))
def representations(n: int) -> tuple[str, str]:
"""Return the base-16 and base-36 representations of n."""
return to_base(n, 16), to_base(n, 36)
Complexity:
- Time: O(log |n|) per base, since each division reduces the value by that base.
- Space: O(log |n|) for the output digits.
Common follow-ups
- What if uppercase output is required? Convert the result to uppercase, or use uppercase digit symbols.
- What if negative values use fixed-width two’s complement? Choose a bit width, mask the value to that width, then convert the masked value.
- How would you support bases above 36? Use a larger symbol alphabet or represent each digit with a separate numeric value.