Solution Explanation for Converting to Base 7

This problem requires converting an integer from base 10 to base 7. The solution involves repeatedly dividing by 7 and collecting the remainders. The remainders, when read in reverse order, form the base 7 representation.

Approach

1. Handle Zero and Negative Numbers: If the input num is 0, return "0". If num is negative, recursively call the function with the absolute value of num and prepend a "-" to the result.

2. Iterative Conversion: The core logic uses an iterative approach. While num is greater than 0:

   • Calculate the remainder when num is divided by 7 (num % 7). This remainder is a digit in the base 7 representation.
   • Add the remainder (converted to a string) to a result string or array.
   • Perform integer division of num by 7 (num //= 7 or num /= 7). This updates num for the next iteration.

3. Reverse the Result: Since the remainders are collected in the order of least significant digit to most significant digit, we reverse the result string or array before returning it.

Time and Space Complexity Analysis

• Time Complexity: O(log7N), where N is the absolute value of the input number. The number of iterations required is proportional to the number of digits in the base 7 representation, which is logarithmic with respect to N.

• Space Complexity: O(log7N) to store the result string or array. The space used is again proportional to the number of digits in the base 7 representation.

Code Examples with Explanations

The code examples below demonstrate the solution in several programming languages. The core logic remains consistent across all languages.

Python:

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])

This Python code efficiently uses a list (ans) to store the digits. The [::-1] slice reverses the list before joining it into a string.

Java:

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();
    }
}

The Java code leverages StringBuilder for efficient string manipulation. The reverse() method is used to reverse the string efficiently.

C++:

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;
    }
};

The C++ code directly concatenates the digits to the ans string in reverse order, making the reversal step implicit within the loop.

Other Languages (Go, TypeScript, Rust): The other language examples follow similar principles, adapting the syntax and data structures to the specific language features. They all implement the core algorithm described above.