Base 7

Problem

Given an integer, return its base 7 string representation.

Example 1:

Input: 100
Output: "202"

Example 2:

Input: -7
Output: "-10"

Note: The input will be in range of [-1e7, 1e7].

Solution

Typical StringBuilder Solution: O(n) time and O(n) space

public class Solution {
    public String convertToBase7(int num) {
        StringBuilder sb = new StringBuilder();
        int abs = Math.abs(num);
        while (abs >= 7) {
            sb.append(abs % 7);
            abs /= 7;
        }
        sb.append(abs);
        String res = sb.reverse().toString();
        return num >= 0 ? res : "-" + res;
    }
}

Concise Recursive Solution: O(n) time and O(n) space

public class Solution {
    public String convertToBase7(int num) {
        if (num < 0) return "-" + convertToBase7(-num);
        if (num < 7) return num + "";
        return convertToBase7(num / 7) + num % 7;
    }
}

Analysis

This is a typical converting number to specific system solution
The first solution is typical, just remember to get absolute value in case num < 0
The recursive solution uses same idea in iterative solution
We need to check the negative first then check num < 7 otherwise negative input returns itself
Notice that we must call recursive method then add num % 7
Because that's how number is converted, put smaller remainder at the end