Base 7
EasyPrompt
Given an integer num, return a string of its base 7 representation.
Example 1:
Input: num = 100
Output: "202"Example 2:
Input: num = -7
Output: "-10"
Constraints:
-107 <= num <= 107
Approaches
2 approaches with complexity analysis and trade-offs.
This approach manually implements the standard algorithm for base conversion. It involves repeatedly taking the remainder and dividing the number by the new base (7) until the number becomes zero. The remainders, which are the digits in the new base, are collected and then reversed to form the final string representation.
Algorithm
- If
numis 0, return "0". - Create a boolean
isNegativeflag, set totrueifnum < 0. - Take the absolute value of
num. - Initialize an empty
StringBuildercalledsb. - While
num > 0:- Append
num % 7tosb. - Set
num = num / 7.
- Append
- If
isNegativeis true, append '-' tosb. - Reverse
sband return its string representation.
Walkthrough
First, handle the edge case where the input num is 0. In this case, the base 7 representation is simply "0".
Determine the sign of the number. If num is negative, store this fact and proceed with the absolute value of num. This simplifies the conversion logic.
Initialize a StringBuilder to build the base 7 string. A StringBuilder is used for efficient string concatenation.
Enter a loop that continues as long as the number is greater than 0.
- In each iteration, calculate the remainder when the number is divided by 7 (
num % 7). This gives the next digit in base 7. - Append this digit to the
StringBuilder. - Update the number by performing integer division by 7 (
num = num / 7).
After the loop terminates, the StringBuilder contains the base 7 digits in reverse order.
If the original number was negative, append the '-' sign to the StringBuilder.
Finally, reverse the StringBuilder to get the correct order of digits and convert it to a String.
class Solution { public String convertToBase7(int num) { if (num == 0) { return "0"; } boolean isNegative = num < 0; if (isNegative) { num = -num; } StringBuilder sb = new StringBuilder(); while (num > 0) { sb.append(num % 7); num /= 7; } if (isNegative) { sb.append('-'); } return sb.reverse().toString(); }}Complexity
Time
O(log₇|num|). The number of iterations in the while loop is determined by how many times we can divide `num` by 7, which is log₇|num|. The operations inside the loop (modulo, division, append) are constant time. The final reversal of the string also takes time proportional to its length, which is log₇|num|.
Space
O(log₇|num|). The space is used by the `StringBuilder` to store the digits of the result. The length of the result is proportional to log₇|num|.
Trade-offs
Pros
Demonstrates a fundamental understanding of number base conversion.
Does not rely on any specific library functions, making it portable.
Cons
Requires more lines of code compared to using a built-in function.
Slightly more complex to implement correctly, with potential for off-by-one or sign errors.
Most programming languages provide built-in functions for converting integers to string representations in different bases. In Java, the Integer.toString(int i, int radix) method can be used to directly solve this problem. This approach is concise, readable, and leverages the highly optimized implementation of the standard library.
Algorithm
- Call the built-in function
Integer.toString(num, 7)with the input numbernumand the desired base7. - Return the resulting string.
Walkthrough
The problem can be solved in a single line of code by calling the appropriate library function.
In Java, the Integer.toString(num, 7) method takes an integer num and a radix (base) 7 and returns the string representation of num in that base.
This method handles positive numbers, negative numbers, and the zero case correctly and efficiently. For example, Integer.toString(100, 7) returns "202", and Integer.toString(-7, 7) returns "-10".
class Solution { public String convertToBase7(int num) { return Integer.toString(num, 7); }}Complexity
Time
O(log₇|num|). The underlying implementation of this function is similar to the manual approach, involving repeated division and remainder operations. Its performance is proportional to the number of digits in the output string.
Space
O(log₇|num|). Space is required to store the characters of the resulting string. The length of the string is proportional to log₇|num|.
Trade-offs
Pros
Extremely simple and concise, leading to highly readable and maintainable code.
Less prone to implementation errors as it relies on a well-tested standard library function.
The library function is often highly optimized, potentially offering better performance than a manual implementation in a high-level language.
Cons
May not be permitted in an interview setting if the goal is to assess the candidate's understanding of the base conversion algorithm itself.
Hides the underlying complexity of the conversion process.
Solutions
Solution
class Solution {public String convertToBase7(int num) { if (num == 0) { return "0"; } if (num < 0) { return "-" + convertToBase7(-num); } StringBuilder sb = new StringBuilder(); while (num != 0) { sb.append(num % 7); num /= 7; } return sb.reverse().toString(); }}class Solution {public: string convertToBase7(int num) { if (num == 0) return "0"; if (num < 0) return "-" + convertToBase7(-num); string ans = ""; while (num) { ans = to_string(num % 7) + ans; num /= 7; } return ans; }};class Solution : def convertToBase7 ( self , num : int ) -> str : if num == 0 : return '0' if num < 0 : return '-' + self . convertToBase7 ( - num ) ans = [] while num : ans . append ( str ( num % 7 )) num //= 7 return '' . join ( ans [:: - 1 ])Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.