Base 7 solution and explanation
Google
9 more videos on this problem
Base 7 - Leetcode 504 - Bit Manipulation (Python)Greg Hogg · 5:20 · 5K views
504. Base 7 | LEETCODE EASYcode Explainer · 4:15 · 1K views
504. Base 7 - Solution | LeetCode ProblemDhruv Pandey · 12:51 · 1K views
504. Base 7 (Leetcode Easy)Programming Live with Larry · 8:51 · 826 views
Base 7 | Leetcode Python Solution | PythonPython Guruji · 12:42 · 767 views
Base 7 | Leetcode - 504 | Approach + Code with explanation.Pirai's Academy · 7:56 · 458 views
LeetCode 504 | Base 7 | Math | Debug | JavaSleepy Cracker · 6:17 · 449 views
504. Base 7 | Leetcode | PythonAbdullah Arshed · 4:09 · 267 views
Base 7 Leetcode 504 | Simple Explanation & C++ Solutionthel3ox · 3:47 · 188 views
LeetCode Çözümleri - 504. Base 7Soner Gönül · 8:30 · 136 views
The problem
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.
def convertToBase7(num: int) -> str:
if num == 0:
return "0"
n = abs(num)
result = []
while n > 0:
result.append(str(n % 7))
n //= 7
if num < 0:
result.append('-')
return ''.join(reversed(result))
print(convertToBase7(100)) # Output: "202"
print(convertToBase7(-7)) # Output: "-10"public class Base7 {
public static String convertToBase7(int num) {
if (num == 0) return "0";
int n = Math.abs(num);
StringBuilder result = new StringBuilder();
while (n > 0) {
result.append(n % 7);
n /= 7;
}
if (num < 0) {
result.append('-');
}
return result.reverse().toString();
}
public static void main(String[] args) {
System.out.println(convertToBase7(100)); // Output: "202"
System.out.println(convertToBase7(-7)); // Output: "-10"
}
}#include <iostream>
#include <string>
using namespace std;
string convertToBase7(int num) {
if (num == 0) return "0";
int n = abs(num);
string result = "";
while (n > 0) {
result = to_string(n % 7) + result;
n /= 7;
}
if (num < 0) {
result = '-' + result;
}
return result;
}
int main() {
cout << convertToBase7(100) << endl; // Output: "202"
cout << convertToBase7(-7) << endl; // Output: "-10"
return 0;
}function convertToBase7(num) {
if (num === 0) return "0";
let n = Math.abs(num);
let result = '';
while (n > 0) {
result = String(n % 7) + result;
n = Math.floor(n / 7);
}
if (num < 0) {
result = '-' + result;
}
return result;
}
console.log(convertToBase7(100)); // Output: "202"
console.log(convertToBase7(-7)); // Output: "-10"#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char* convertToBase7(int num) {
if (num == 0) return "0";
int n = abs(num);
char buffer[50];
int index = 0;
while (n > 0) {
buffer[index++] = '0' + (n % 7);
n /= 7;
}
if (num < 0) {
buffer[index++] = '-';
}
for (int i = 0; i < index / 2; ++i) { // Reverse the string
char temp = buffer[i];
buffer[i] = buffer[index - i - 1];
buffer[index - i - 1] = temp;
}
buffer[index] = '\0';
return strdup(buffer);
}
int main() {
int num = 100;
printf("%s\n", convertToBase7(num)); // Output: "202"
num = -7;
printf("%s\n", convertToBase7(num)); // Output: "-10"
return 0;
}using System;
public class Base7 {
public static string ConvertToBase7(int num) {
if (num == 0) return "0";
int n = Math.Abs(num);
var result = new System.Text.StringBuilder();
while (n > 0) {
result.Append(n % 7);
n /= 7;
}
if (num < 0) {
result.Append('-');
}
char[] charArray = result.ToString().ToCharArray();
Array.Reverse(charArray);
return new string(charArray);
}
public static void Main() {
Console.WriteLine(ConvertToBase7(100)); // Output: "202"
Console.WriteLine(ConvertToBase7(-7)); // Output: "-10"
}
}In Python, we append digits to a list, which is later reversed and joined to form the final string representation. Using a list helps with appending and reversing operations efficiently.
Time Complexity: O(log7(n))
Space Complexity: O(log7(n))
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.
def convertToBase7(num: int) -> str:
def helper(n: int) -> str:
if n < 7:
return str(n)
return helper(n // 7) + str(n % 7)
if num == 0:
return "0"
result = helper(abs(num))
return '-' + result if num < 0 else result
print(convertToBase7(100)) # Output: "202"
print(convertToBase7(-7)) # Output: "-10"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.
Time Complexity: O(log7(n))
Space Complexity: O(log7(n)), due to recursion depth.
Approach 3: Default Approach
function convertToBase7(num: number): string {
if (num == 0) {
return '0';
}
let res = '';
const isMinus = num < 0;
if (isMinus) {
num = -num;
}
while (num != 0) {
const r = num % 7;
res = r + res;
num = (num - r) / 7;
}
return isMinus ? '-' + res : res;
}func convertToBase7(num int) string {
if num == 0 {
return "0"
}
if num < 0 {
return "-" + convertToBase7(-num)
}
ans := []byte{}
for num != 0 {
ans = append([]byte{'0' + byte(num%7)}, ans...)
num /= 7
}
return string(ans)
}impl Solution {
pub fn convert_to_base7(mut num: i32) -> String {
if num == 0 {
return String::from("0");
}
let mut res = String::new();
let is_minus = num < 0;
if is_minus {
num = -num;
}
while num != 0 {
res.push_str((num % 7).to_string().as_str());
num /= 7;
}
if is_minus {
res.push('-');
}
res.chars().rev().collect()
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Iterative Division Approach | Time Complexity: O(log7(n)) |
| Recursive Division Approach | Time Complexity: O(log7(n)) |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Division | O(log₇ n) | O(log₇ n) | General case; simplest and most interview‑friendly implementation |
| Recursive Division | O(log₇ n) | O(log₇ n) | When demonstrating recursion patterns or recursive number decomposition |
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.