504. Base 7

Problem Description

The problem requires writing a function that converts an integer num to its base 7 representation. In a base 7 number system, each digit in a number represents an increasing power of 7, starting from the rightmost digit (7^0, 7^1, 7^2, and so forth). The digits can only be from 0 to 6, inclusive. The output of the function should be a string representing the number in base 7.

For example, if the input is 100, the output should be '202' because 100 equals 2 × 7^2 + 0 × 7^1 + 2 × 7^0 .

Edge cases to consider include when the input number is 0, where the base 7 representation is also '0', and when the number is negative, in which case the base 7 representation should include a negative sign ('-') before the digits.

Intuition

To arrive at a solution, we break down the problem and approach it step by step:

Handling Zero: If the input number is 0, then the base 7 representation is straightforwardly '0'.
Handling Negatives: If the number is negative, we work with its absolute value and prepend a '-' to the result after the base 7 conversion.
Conversion to Base 7: For a positive number, we can iteratively divide the number by 7 and keep track of the remainders. Each remainder gives us the base 7 digit starting from the least significant digit to the most significant digit.
Reversal and Joining Digits: Since the remainders are obtained in reverse order (least significant digit first), we reverse the sequence of remainders and concatenate them to form the base 7 string. This is where we utilize the array structure to store digits and the join and [::-1] operations to form the final string.

Learn more about Math patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

dp[i] = dp[i] + 1dp[i] = dp[i] + dp[i - 1]dp[i] = (dp[i] + dp[j] + 1) for j in 0 to idp[i] = max(dp[i], dp[j] + 1) for j in 0 to i

I don’t know

Solution Approach

The solution utilizes a simple algorithm that converts an integer from base 10 to base 7. Here's a step-by-step walkthrough of the implementation corresponding to the provided solution code:

Check for Zero: The code checks whether the input num is 0. If it is, it immediately returns the string '0' because zero is represented the same in any base.
Handling Negative Numbers: If num is negative, we convert it to a positive number using -num and perform a recursive call to convertToBase7. We prepend a '-' to the result of the recursive call to account for the negative sign. This ensures that the base 7 conversion logic only deals with positive numbers.
Conversion Loop: A while loop is used to perform the base 7 conversion. Inside the loop, the remainder of num divided by 7 is calculated using num % 7. This gives us the next digit of the base 7 number (from right to left).
Storing Digits: The remainders/digits are stored in an array called ans. Each digit is converted to a string before appending it to the array. This is done because the output needs to be a string, and it's more efficient to build an array of strings and then join them together than to perform string concatenation in each iteration.
Updating the Number: The number num is then updated by performing integer division by 7 using num //= 7. Integer division ensures that we get the next set of digits for the remaining number without decimals.
Reversing and Joining: Once the number num is reduced to 0, all of its base 7 digits are contained in ans array but in reverse order. The ans[::-1] expression reverses the array. To form the final base 7 string, the code joins the elements of this reversed array using ''.join(ans[::-1]).

The concepts of recursion, string manipulation, and number base conversion are applied in this solution. The problem is solved without using any complex data structures or patterns, focusing on simple loop iteration and string array handling.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of these properties could exist for a graph but not a tree?

Contain cyclesThere are multiple ways to traverseConnectedHas no cycle

I don’t know

Example Walkthrough

Let's consider the number 58 to illustrate the solution approach. We want to convert 58 into its base 7 representation.

Check for Zero: Since 58 is not 0, this step is skipped.
Handling Negative Numbers: 58 is positive, so there is no need to handle negatives. We proceed directly with the base 7 conversion.
Conversion Loop: We start by dividing 58 by 7. The remainder is 58 % 7 = 2. This is the least significant digit of the base 7 representation.
Storing Digits: The remainder 2 is added to the array ans. It's stored as a string '2', so ans = ['2'] now.
Updating the Number: Next, we update 58 by doing integer division by 7: 58 // 7 = 8. We repeat the loop with this new number 8.
- Divide 8 by 7 again. The remainder is 8 % 7 = 1. Add '1' to ans, which becomes ans = ['2', '1'].
- Update 8 by doing integer division by 7: 8 // 7 = 1.
Now we have 1, which is still positive, so we continue.
- Divide 1 by 7. The remainder is 1 % 7 = 1. Add '1' to ans, which now becomes ans = ['2', '1', '1'].
- Update 1 by doing integer division by 7: 1 // 7 = 0. Now that num is 0, the conversion loop ends.
Reversing and Joining: The array ans currently contains ['2', '1', '1']. This is the reverse of what we want, so we need to reverse it back to get the correct order, which gives us ['1', '1', '2'].

Finally, we join these digits together to get the base 7 representation of 58: ''.join(['1', '1', '2']) which results in '112'.

So, the base 7 representation of the decimal number 58 is '112'.

Solution Implementation

1class Solution:
2    def convertToBase7(self, num: int) -> str:
3        # Handle the special case where num is zero
4        if num == 0:
5            return '0'
6      
7        # Check if the number is negative, if so, convert the number to positive
8        # and prepend the negative sign after the base 7 conversion.
9        if num < 0:
10            return '-' + self.convertToBase7(-num)
11      
12        # Initialize a list to hold the digits of the base 7 representation.
13        base7_digits = []
14      
15        # Convert the number to base 7.
16        while num > 0:
17            # Append the remainder (base 7 digit) to the list.
18            base7_digits.append(str(num % 7))
19            # Update num by dividing it by 7.
20            num //= 7
21      
22        # Join the base 7 digits in reverse order to form the final base 7 number.
23        # Since we append digits from least significant to most significant,
24        # we need to reverse the list before joining into a string.
25        return ''.join(reversed(base7_digits))
26
27# Example usage:
28# solution = Solution()
29# base7_number = solution.convertToBase7(100)
30# print(base7_number) # Output would be the base 7 representation of 100
31

1class Solution {
2
3    /**
4     * This method converts an integer to its base 7 representation.
5     * 
6     * @param num The integer to be converted to base 7.
7     * @return A string representing the base 7 equivalent of the input number.
8     */
9    public String convertToBase7(int num) {
10        // Base case: If the input is zero, return "0" as its base 7 representation.
11        if (num == 0) {
12            return "0";
13        }
14
15        // If the number is negative, return the negative sign concatenated
16        // with the base 7 representation of the positive counterpart.
17        if (num < 0) {
18            return "-" + convertToBase7(-num);
19        }
20
21        // Create a StringBuilder to construct the base 7 representation
22        StringBuilder builder = new StringBuilder();
23
24        // Continue the process until we have completely converted the number to base 7
25        while (num != 0) {
26            // Append the remainder (base 7 digit) to the StringBuilder
27            builder.append(num % 7);
28
29            // Divide the number by 7 to get to the next digit
30            num /= 7;
31        }
32
33        // Reverse the string since the construction was from least significant digit to most
34        // significant.
35        return builder.reverse().toString();
36    }
37}
38

1class Solution {
2public:
3    // Function to convert an integer to its base 7 string representation
4    string convertToBase7(int num) {
5        // Handle the base case where number is 0
6        if (num == 0) {
7            return "0";
8        }
9      
10        // If the number is negative, recursively call the function on its absolute value
11        // and append a minus sign to the result.
12        if (num < 0) {
13            return "-" + convertToBase7(-num);
14        }
15      
16        // Initialize an empty string to hold the base 7 representation
17        string base7Representation = "";
18      
19        // Loop to convert the number to base 7
20        while (num > 0) {
21            // Prepend the remainder of the division by 7 to the string
22            base7Representation = to_string(num % 7) + base7Representation;
23            // Divide the number by 7 to get the next digit
24            num /= 7;
25        }
26      
27        // Return the resulting base 7 string
28        return base7Representation;
29    }
30};
31

1/**
2 * Converts an integer to its base-7 string representation.
3 * @param {number} num - The integer to be converted.
4 * @return {string} The base-7 representation of the given number.
5 */
6function convertToBase7(num: number): string {
7    // If the number is zero, return the string "0".
8    if (num === 0) {
9        return '0';
10    }
11
12    // Initialize the result string.
13    let result = '';
14    // Determine if the number is negative.
15    const isNegative = num < 0;
16  
17    // If the number is negative, convert it to positive.
18    if (isNegative) {
19        num = -num;
20    }
21
22    // Loop to divide the number by 7 and take the remainder until num is 0.
23    while (num !== 0) {
24        // Calculate the remainder of num divided by 7.
25        const remainder = num % 7;
26        // Prepend the remainder to the result string.
27        result = remainder.toString() + result;
28        // Update num to be the quotient of division by 7.
29        num = (num - remainder) / 7;
30    }
31
32    // If the original number was negative, add the negative sign to the result.
33    return isNegative ? '-' + result : result;
34}
35

Not Sure What to Study? Take the 2-min Quiz：

Time and Space Complexity

Time Complexity

The time complexity of the convertToBase7 function mainly depends on the number of digit extractions performed in the loop. Since each iteration of the loop processes one digit of the number in base 7, the number of iterations is O(log_7(num)). However, when evaluating time complexity in terms of base 2 (which is common since our input size is commonly measured in bits), it's safe to say that it is approximately O(log(num)) because the base of the logarithm can be changed with a constant multiplier due to the logarithm change of base property (log_b(a) = log_c(a) / log_c(b)), and constants are discarded in big O notation.

The methods append and str have constant time complexity O(1), and join is O(n) where n is the length of the list ans. But since the length of ans contributes to the overall time it takes to construct the base 7 representation, this doesn't add more than a constant multiple to the log(num) term.

Therefore, the time complexity of the given code is O(log(num)).

Space Complexity

Space complexity includes the extra space required besides the input. In this case, it is determined by the space needed to hold the ans list and the characters it contains.

For a decimal number num, the number of digits d in its base 7 representation will be roughly log_7(num), which is about O(log(num)). Each digit converts to a string element in the ans list, so the space complexity is directly proportional to the number of digits in the base 7 representation.

So, the space complexity of the given code is also O(log(num)) as it is solely dependent on the length of the ans list.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

504. Base 7

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Time Complexity

Space Complexity

Recommended Readings