504. Base 7
Model: qwen2.5-coder:14b
Topics:
FAANG asked: 0
Acceptance rate: 46.5%
Problem Breakdown
The problem asks us to convert an integer into its base 7 representation. The input is a single integer within the range of [-1e7, 1e7]. The output should be a string representing the number in base 7. We need to handle both positive and negative numbers correctly.
Inputs:
- An integer
numin the range of [-1e7, 1e7].
Outputs:
- A string representing the integer in base 7.
Implicit Constraints or Tricky Edge Cases:
- Negative numbers.
- Zero (as a special case).
- The maximum and minimum values within the given range.
Intuition
The brute-force approach would involve repeatedly dividing the number by 7 and keeping track of the remainders until the quotient becomes zero. However, this approach is straightforward but not optimal in terms of readability or efficiency.
A better approach involves understanding how base conversion works. For any base conversion, we need to handle both positive and negative numbers separately. The key insight is that for negative numbers, we can first convert their absolute value and then add a negative sign at the end. This simplifies the logic since we only need to deal with non-negative numbers during the conversion process.
Approach
- Check for Zero: If the input number is zero, return “0” immediately.
- Handle Negative Numbers: Convert the number to its absolute value and keep track of whether it was negative.
- Base Conversion:
- Initialize an empty list to store the digits of the base 7 representation.
- While the number is greater than zero:
- Compute the remainder when the number is divided by 7.
- Append this remainder to the list of digits.
- Update the number by performing integer division by 7.
- Construct the Result String:
- Reverse the list of digits to get the correct order.
- Convert each digit to a string and join them together.
- If the original number was negative, prepend a ’-’ sign to the result.
- Return the Result: The final string is the base 7 representation of the input number.
Complexity Analysis
- Time Complexity: O(log₇(n)), where n is the absolute value of the input number. This is because we are repeatedly dividing the number by 7 until it becomes zero.
- Space Complexity: O(log₇(n)), used to store the digits of the base 7 representation.
Solution
def convertToBase7(num: int) -> str:
if num == 0:
return "0"
is_negative = num < 0
num = abs(num)
digits = []
while num > 0:
remainder = num % 7
digits.append(str(remainder))
num //= 7
if is_negative:
digits.append('-')
return ''.join(reversed(digits))
# Example usage:
# print(convertToBase7(100)) # Output: "202"
# print(convertToBase7(-7)) # Output: "-10"
Edge Cases Handled
- Zero: The function returns “0” immediately if the input is zero.
- Negative Numbers: The function correctly handles negative numbers by converting their absolute value and adding a ’-’ sign at the end.
- Maximum and Minimum Values: The function works efficiently for the maximum and minimum values within the given range, as it only depends on the number of digits in the base 7 representation.