# LeetCode 504: Base 7

## Problem Restatement

We are given an integer `num`.

We need to return its representation in base `7` as a string.

The official problem asks us to convert an integer from base 10 into base 7. Negative numbers should keep the negative sign. ([leetcode.com](https://leetcode.com/problems/base-7/?utm_source=chatgpt.com))

## Input and Output

| Item | Meaning |
|---|---|
| Input | An integer `num` |
| Output | A string |
| Goal | Return the base 7 representation of `num` |

Function shape:

```python
class Solution:
    def convertToBase7(self, num: int) -> str:
        ...
```

## Examples

Example 1:

```python
num = 100
```

We repeatedly divide by `7`.

The remainders are:

```text
100 % 7 = 2
14 % 7 = 0
2 % 7 = 2
```

Reading remainders from bottom to top gives:

```text
202
```

So the answer is:

```python
"202"
```

Example 2:

```python
num = -7
```

The base 7 representation of `7` is:

```text
10
```

Preserve the negative sign:

```python
"-10"
```

## First Thought: Use Repeated Division

This problem follows the standard base conversion process.

For a positive number:

1. Divide by `7`.
2. Record the remainder.
3. Continue with the quotient.
4. Reverse the collected digits.

The remainder gives the next digit in base `7`.

For example:

```text
100 / 7 = 14 remainder 2
14 / 7 = 2 remainder 0
2 / 7 = 0 remainder 2
```

So the digits are:

```text
2, 0, 2
```

Reversed:

```text
202
```

## Key Insight

The least significant digit of a base `b` representation is always:

```text
num % b
```

After removing that digit:

```text
num //= b
```

So repeated modulo and integer division gradually build the representation.

For this problem:

```text
b = 7
```

## Algorithm

Handle the special case:

```python
num == 0
```

because its representation is simply:

```python
"0"
```

Then:

1. Record whether the number is negative.
2. Work with the absolute value.
3. Repeatedly:
   - append `num % 7`
   - update `num //= 7`
4. Reverse the digits.
5. Add the negative sign if needed.

## Correctness

At every step, the algorithm extracts:

```text
num % 7
```

which is exactly the least significant base 7 digit of the current number.

Integer division:

```text
num // 7
```

removes that least significant digit from further consideration.

Repeating this process eventually reduces the number to `0`.

The collected digits are generated from least significant to most significant order, so reversing them produces the correct base 7 representation.

If the original number was negative, prepending `"-"` gives the correct signed representation.

Therefore the algorithm returns the correct base 7 string.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(log₇ n)` | One iteration per base 7 digit |
| Space | `O(log₇ n)` | Stores the generated digits |

The number of digits in base `7` is proportional to:

```text
log₇ n
```

## Implementation

```python
class Solution:
    def convertToBase7(self, num: int) -> str:
        if num == 0:
            return "0"

        negative = num < 0
        num = abs(num)

        digits = []

        while num > 0:
            digits.append(str(num % 7))
            num //= 7

        result = "".join(reversed(digits))

        if negative:
            result = "-" + result

        return result
```

## Code Explanation

Handle the zero case first:

```python
if num == 0:
    return "0"
```

Without this case, the loop would generate no digits.

Track whether the number was negative:

```python
negative = num < 0
```

Then work with the absolute value:

```python
num = abs(num)
```

The digits are stored in a list:

```python
digits = []
```

Each iteration extracts one base 7 digit:

```python
digits.append(str(num % 7))
```

Then remove the extracted digit:

```python
num //= 7
```

The digits were generated backwards, so reverse them:

```python
result = "".join(reversed(digits))
```

Finally, restore the negative sign if necessary:

```python
if negative:
    result = "-" + result
```

## Testing

```python
def test_convert_to_base7():
    s = Solution()

    assert s.convertToBase7(100) == "202"
    assert s.convertToBase7(-7) == "-10"
    assert s.convertToBase7(0) == "0"
    assert s.convertToBase7(7) == "10"
    assert s.convertToBase7(49) == "100"
    assert s.convertToBase7(1) == "1"

    print("all tests passed")
```

Test meaning:

| Test | Why |
|---|---|
| `100` | Standard multi-digit conversion |
| `-7` | Negative number handling |
| `0` | Special base case |
| `7` | Exact power transition |
| `49` | Multiple zeros in representation |
| `1` | Smallest positive number |