Problem Description

Given an integer n, you need to format it by adding dots (".") as thousands separators and return the formatted number as a string.

The problem asks you to take any non-negative integer and insert dots every three digits from the right to make the number more readable. For example:

• Input: 987 → Output: "987" (no separator needed)
• Input: 1234 → Output: "1.234"
• Input: 123456789 → Output: "123.456.789"
• Input: 0 → Output: "0"

The solution works by extracting digits from right to left using division and modulo operations. It keeps a counter to track when to insert a dot (every 3 digits). The digits and dots are collected in a list, then reversed and joined to form the final string since we process the number from right to left but need to display it from left to right.

The key steps in the algorithm are:

1. Extract the rightmost digit using divmod(n, 10)
2. Add the digit to the result list
3. Increment a counter
4. If we've processed 3 digits and there are more digits to process, add a dot
5. Continue until all digits are processed
6. Reverse the result list and join into a string

Intuition

When we need to add thousands separators to a number, the natural way to think about it is from right to left - we place a dot after every group of 3 digits starting from the rightmost position. This mirrors how we naturally read large numbers: we group digits in threes from the right.

The challenge is that we need to process the number from right to left (to know where to place dots), but strings are typically built from left to right. This suggests we should extract digits from the right side of the number.

To extract digits from right to left, we can repeatedly use the modulo operation n % 10 to get the rightmost digit, and integer division n // 10 to remove that digit from the number. This is a standard technique for digit extraction.

As we extract each digit, we need to track how many consecutive digits we've processed without adding a separator. Once we hit 3 digits, we insert a dot and reset our counter. The key insight is that we only add a dot if there are more digits to process (when n > 0 after division), preventing unnecessary dots at the beginning of the number.

Since we're building the result from right to left but need to display it from left to right, we collect everything in a list and reverse it at the end. This is more efficient than string concatenation and gives us the correct left-to-right ordering.

The divmod(n, 10) function elegantly combines both operations we need - getting the quotient (remaining number) and remainder (current digit) in one step, making the code cleaner and slightly more efficient.

Solution Approach

The implementation uses a digit extraction approach with a counter to track when to insert separators.

We initialize two variables:

• cnt = 0: A counter to track how many digits we've processed in the current group
• ans = []: A list to store the digits and dots as we build the result

The main loop continues indefinitely with while 1: and processes the number digit by digit:

1. Extract digit: Use divmod(n, 10) to simultaneously get:

   • n: The quotient (remaining number after removing the rightmost digit)
   • v: The remainder (the rightmost digit)

2. Store digit: Convert the digit v to string and append to ans list

3. Update counter: Increment cnt to track we've processed one more digit

4. Check termination: If n == 0, we've processed all digits and break from the loop

5. Insert separator: If cnt == 3 (we've collected 3 digits), we:

   • Append a dot '.' to the list
   • Reset cnt = 0 to start counting the next group

The crucial part is that we check for separator insertion after checking if n == 0. This ensures we don't add an unnecessary dot at the beginning of the number (which would appear at the end before reversal).

Finally, since we built the result from right to left, we reverse the list with ans[::-1] and join all elements into a string with ''.join().

For example, with input 1234:

• First iteration: Extract 4, ans = ['4'], cnt = 1
• Second iteration: Extract 3, ans = ['4', '3'], cnt = 2
• Third iteration: Extract 2, ans = ['4', '3', '2'], cnt = 3, add dot: ans = ['4', '3', '2', '.'], reset cnt = 0
• Fourth iteration: Extract 1, ans = ['4', '3', '2', '.', '1'], cnt = 1
• n = 0, break
• Reverse and join: '1.234'

Example Walkthrough

Let's walk through the algorithm with the input n = 12345:

Initial State:

• n = 12345
• cnt = 0 (digit counter)
• ans = [] (result list)

Iteration 1:

• divmod(12345, 10) → n = 1234, v = 5
• Add '5' to ans: ans = ['5']
• Increment counter: cnt = 1
• Check if done: n = 1234 (not zero, continue)
• Check separator: cnt = 1 (not 3, no separator needed)

Iteration 2:

• divmod(1234, 10) → n = 123, v = 4
• Add '4' to ans: ans = ['5', '4']
• Increment counter: cnt = 2
• Check if done: n = 123 (not zero, continue)
• Check separator: cnt = 2 (not 3, no separator needed)

Iteration 3:

• divmod(123, 10) → n = 12, v = 3
• Add '3' to ans: ans = ['5', '4', '3']
• Increment counter: cnt = 3
• Check if done: n = 12 (not zero, continue)
• Check separator: cnt = 3 (equals 3, add separator!)
• Add dot and reset: ans = ['5', '4', '3', '.'], cnt = 0

Iteration 4:

• divmod(12, 10) → n = 1, v = 2
• Add '2' to ans: ans = ['5', '4', '3', '.', '2']
• Increment counter: cnt = 1
• Check if done: n = 1 (not zero, continue)
• Check separator: cnt = 1 (not 3, no separator needed)

Iteration 5:

• divmod(1, 10) → n = 0, v = 1
• Add '1' to ans: ans = ['5', '4', '3', '.', '2', '1']
• Increment counter: cnt = 2
• Check if done: n = 0 (zero, exit loop!)

Final Step:

• Reverse the list: ['1', '2', '.', '3', '4', '5']
• Join into string: "12.345"

The key insight is that we process digits from right to left (5→4→3→2→1), inserting a dot after every third digit. By reversing at the end, we get the correct left-to-right representation with dots properly placed as thousands separators.

Solution Implementation

Time and Space Complexity

Time Complexity: O(d) where d is the number of digits in the integer n.

The algorithm processes each digit of the number exactly once. In each iteration of the while loop:

• divmod(n, 10) operation takes O(1) time
• Appending to the list takes O(1) amortized time
• String conversion and other operations are O(1)

Since the number of digits in n is ⌊log₁₀(n)⌋ + 1 for n > 0 (or 1 for n = 0), the loop runs d times. The final ans[::-1] reversal takes O(d) time, and ''.join() also takes O(d) time. Therefore, the overall time complexity is O(d) + O(d) + O(d) = O(d).

Space Complexity: O(d) where d is the number of digits in the integer n.

The space is used for:

• The ans list which stores all digits plus separators. In the worst case, this contains approximately d + ⌊(d-1)/3⌋ elements (digits plus dots)
• The reversed list created by ans[::-1] which has the same size
• The final string created by ''.join() which has the same size

All these are proportional to the number of digits d, resulting in a space complexity of O(d).

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

Common Pitfalls

1. Adding Extra Separator at the Beginning

One of the most common mistakes is placing the separator check before the termination condition, which results in an extra dot at the beginning of numbers with digits that are multiples of 3.

Incorrect Implementation:

def thousandSeparator(self, n: int) -> str:
    digit_count = 0
    result = []
  
    while True:
        n, digit = divmod(n, 10)
        result.append(str(digit))
        digit_count += 1
      
        # Wrong: Checking separator BEFORE termination
        if digit_count == 3:
            result.append('.')
            digit_count = 0
          
        if n == 0:
            break
  
    return ''.join(result[::-1])

Problem: For input 123, this produces ".123" instead of "123" because we add a dot after processing the third digit even though there are no more digits left.

Solution: Always check if there are more digits to process (n == 0) before adding a separator. The correct order is:

1. Process digit
2. Check if we're done
3. Only then add separator if needed

2. Handling Edge Case of Zero

Another pitfall is not properly handling when the input is 0. Some implementations might return an empty string or fail to process zero correctly.

Incorrect Approach:

def thousandSeparator(self, n: int) -> str:
    if n == 0:
        return ""  # Wrong: should return "0"
    # ... rest of the code

Solution: The algorithm should naturally handle 0 without special casing. When n = 0, the first iteration extracts the digit 0, adds it to the result, then breaks since n becomes 0.

3. Using String Concatenation Instead of List

Building the result using string concatenation in a loop is inefficient due to string immutability in Python.

Inefficient Implementation:

def thousandSeparator(self, n: int) -> str:
    result = ""  # Using string instead of list
    digit_count = 0
  
    while True:
        n, digit = divmod(n, 10)
        result = str(digit) + result  # String concatenation
        digit_count += 1
      
        if n == 0:
            break
          
        if digit_count == 3:
            result = "." + result  # More string concatenation
            digit_count = 0
  
    return result

Problem: Each string concatenation creates a new string object, leading to O(n²) time complexity where n is the number of digits.

Solution: Use a list to collect characters and join them at the end. This maintains O(n) time complexity.

4. Incorrect Counter Reset Logic

Forgetting to reset the counter after adding a separator or resetting it at the wrong time.

Incorrect:

if digit_count == 3:
    result.append('.')
    # Forgot to reset: digit_count = 0

This would cause dots to be placed incorrectly after the first group of three digits.

Solution: Always reset the counter immediately after adding a separator to start counting the next group of three digits.