Skip to main content
Talentd

Base 7 - Solution & Explanation

EasyMath10 min readAsked at: Amazon, Microsoft, Google +1
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: Given an integer num, return its representation in base 7 as a string. The task is essentially base conversion: repeatedly divide the number by 7 and collect the remainders that form the digits of the base‑7 number.

Approach 1: Iterative Division Approach (O(log7 n) time, O(log7 n) space)

The standard base conversion technique repeatedly divides the number by the target base and records the remainder. Start with num, compute num % 7 to get the least significant base‑7 digit, then update num = num // 7. Continue until the number becomes zero. Because digits are produced from least significant to most significant, append them to a buffer and reverse at the end (or prepend each digit). Handle negative numbers by storing the sign and converting the absolute value first. This approach runs in O(log7 n) time because each division reduces the number by a factor of 7, and it uses O(log7 n) space for the resulting string. The logic relies purely on arithmetic operations from math, making it simple and efficient.

Approach 2: Recursive Division Approach (O(log7 n) time, O(log7 n) space)

The same division idea can be expressed recursively. Instead of building digits iteratively, recursively process num // 7 until the base case (num < 7) is reached. Each recursive call returns the base‑7 representation of the higher digits, and the current remainder num % 7 is appended to the result. The recursion depth equals the number of base‑7 digits, which is O(log7 n). Space complexity is also O(log7 n) due to the call stack. This style highlights the natural decomposition of the number into higher digits and the current digit, a common pattern in recursion problems involving numeric representation.

Both approaches rely on the same mathematical insight: any number in base 10 can be represented as repeated divisions by the new base, collecting remainders as digits. The iterative version builds the result explicitly with a loop, while the recursive version constructs it during the return phase of function calls.

Recommended for interviews: The iterative division approach is typically expected. It demonstrates that you understand base conversion mechanics and can implement it efficiently using simple arithmetic operations. The recursive approach is clean and expressive but adds call‑stack overhead, so it’s better presented as an alternative after explaining the iterative method. Showing both reinforces your understanding of number representation and basic math transformations.

Approach 1: Iterative Division Approach

This approach involves converting the number to base 7 by repeatedly dividing the number by 7 and noting the remainders. This is similar to how you would convert a decimal number to any other base. We gather the remainders which will form the digits of the number in base 7, with the first remainder being the least significant digit.

We first handle the case for the number being 0. For non-zero numbers, we compute the absolute value, repeatedly divide by 7 to obtain remainders, and store them as characters in a buffer. If the number was negative, we append a '-' after collecting all digits. Finally, the digits are reversed to correct order before returning the string.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(log7(n)), where n is the absolute value of the input number. This is due to the division operations required to reduce the number to zero.
Space Complexity: O(log7(n)), due to the storage required for the result string in base 7.

Try this approach in the editor →

Approach 2: Recursive Division Approach

This recursive approach streamlines handling the conversion by leveraging function calls to manage the digit placement. Rather than manually reversing the digits collected as in the iterative method, recursion inherently processes the most significant digit later, accommodating natural string assembly order.

The function helper is defined to perform the recursive conversions. It divides the number by 7, recursively processing all digits. The base case handles digits less than 7 directly. Negative numbers are managed by post-fixing a negative sign if the original number is negative.

Code

Python

Python

Complexity

Time Complexity: O(log7(n))
Space Complexity: O(log7(n)), due to recursion depth.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Iterative Division Approach

Time Complexity: O(log7(n)), where n is the absolute value of the input number. This is due to the division operations required to reduce the number to zero.
Space Complexity: O(log7(n)), due to the storage required for the result string in base 7.

Recursive Division Approach

Time Complexity: O(log7(n))
Space Complexity: O(log7(n)), due to recursion depth.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Iterative DivisionO(log₇ n)O(log₇ n)General case; simplest and most interview‑friendly implementation
Recursive DivisionO(log₇ n)O(log₇ n)When demonstrating recursion patterns or recursive number decomposition

Video Solution

Base 7 - Leetcode 504 - Bit Manipulation (Python) • Greg Hogg • 5,277 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Base 7 easy or hard?
Base 7 is categorized as an easy problem. The core idea is simple base conversion using division and remainder. Candidates mainly need to handle negative numbers and build the digits in the correct order.
How to solve Base 7 in O(n)?
The problem is typically solved in O(log₇ n) time rather than O(n). Each division by 7 reduces the number significantly, and the number of iterations equals the number of digits in base 7. Implement a loop that repeatedly computes remainder (num % 7) and integer division (num // 7) until the value reaches zero.
What is the best approach for Base 7?
The iterative division approach is the most practical solution. Repeatedly divide the number by 7, record the remainder as the next digit, and continue until the number becomes zero. Reverse the collected digits to form the final base‑7 string. This method runs in O(log₇ n) time and uses O(log₇ n) space for the result.
What data structure is used in Base 7?
No complex data structure is required. The solution mainly uses arithmetic operations and a string or character buffer to store digits as they are generated. The algorithm belongs to the math category and sometimes uses recursion if implemented recursively.
What is the time complexity of Base 7?
The time complexity is O(log₇ n). Each step divides the number by 7, so the total number of operations equals the number of base‑7 digits in the number. Space complexity is also O(log₇ n) because the output string contains that many digits.
Base 7 Python or Java solution approach?
Both Python and Java implementations follow the same logic: repeatedly divide the number by 7 and append the remainder to a result string or builder. Python often uses string concatenation or a list that is reversed, while Java typically uses a StringBuilder for efficient digit construction.
Is Base 7 asked at Google, Amazon, or Meta?
Base conversion problems like Base 7 occasionally appear in interviews at large tech companies because they test basic number manipulation and reasoning about arithmetic operations. While not among the most frequent questions, it represents the type of simple math and implementation problem candidates should handle quickly.

Ready to solve this problem?

Practice Base 7 with our built-in code editor and test cases.

Practice on FleetCode
Previous

Add Two Numbers

Next

Reverse Integer