Code Implementation

class Solution:
    def thousandSeparator(self, n: int) -> str:
        s = str(n)
        res = []
        count = 0
        for ch in reversed(s):
            if count and count % 3 == 0:
                res.append('.')
            res.append(ch)
            count += 1
        return ''.join(reversed(res))
      

class Solution {
public:
    string thousandSeparator(int n) {
        string s = to_string(n);
        string res = "";
        int count = 0;
        for (int i = s.size() - 1; i >= 0; --i) {
            if (count && count % 3 == 0) res = '.' + res;
            res = s[i] + res;
            count++;
        }
        return res;
    }
};
      

class Solution {
    public String thousandSeparator(int n) {
        String s = Integer.toString(n);
        StringBuilder res = new StringBuilder();
        int count = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            if (count > 0 && count % 3 == 0) {
                res.append('.');
            }
            res.append(s.charAt(i));
            count++;
        }
        return res.reverse().toString();
    }
}
      

var thousandSeparator = function(n) {
    let s = n.toString();
    let res = [];
    let count = 0;
    for (let i = s.length - 1; i >= 0; i--) {
        if (count > 0 && count % 3 === 0) res.push('.');
        res.push(s[i]);
        count++;
    }
    return res.reverse().join('');
};
      

Problem Description

The "Thousand Separator" problem asks you to format a given integer n into a string representation where every three digits are separated by a dot ('.'), starting from the right. For example, if n = 123456789, the expected output is "123.456.789". If the number has less than four digits, it should be returned as-is, without any separator.

Key constraints:

• Only digits, and separators (dots) are allowed in the output string.
• No leading or trailing separators.
• If n is 0, the output is "0".
• There is always exactly one valid formatting for each input.

Thought Process

The problem is essentially about string formatting: grouping digits in sets of three from the right, and inserting a dot between groups. The naive (brute-force) approach would be to convert the number to a string, then insert separators by counting digits from the right.

The main challenge is to handle the grouping correctly, especially for numbers whose length is not a multiple of three. We also need to avoid unnecessary separators at the start or end of the string.

An optimized approach is to iterate through the string representation of n from right to left, appending a dot after every three digits (except at the end), and then reverse the result to get the correct order.

Solution Approach

• Step 1: Convert the Integer to String
  Since we need to work with individual digits and insert separators, we first convert n to its string representation.
• Step 2: Iterate from Right to Left
  Starting from the least significant digit (the rightmost), we process each digit and keep track of how many digits we've added so far.
• Step 3: Insert Separators
  After every three digits (except if we've reached the end), insert a dot before adding the next group of digits.
• Step 4: Build the Result
  Since we're processing in reverse order, we can append digits and separators to a list or string builder, then reverse it at the end to get the correct order.
• Step 5: Return the Formatted String
  Join the characters and return the final formatted string.

This approach is efficient because it processes each digit exactly once and only needs a single pass through the string.

Example Walkthrough

Let's take n = 123456789 as an example:

1. Convert to string: "123456789"
2. Start from the right:
   • Add '9' (count = 1)
   • Add '8' (count = 2)
   • Add '7' (count = 3)
   • Since count is now 3, add a dot before next digit
   • Add '6' (count = 4)
   • Add '5' (count = 5)
   • Add '4' (count = 6)
   • Since count is now 6, add another dot before next digit
   • Add '3' (count = 7)
   • Add '2' (count = 8)
   • Add '1' (count = 9)
3. Reverse the result: "123.456.789"

For a smaller number, like n = 123:

• Convert to string: "123"
• Process digits: '3', '2', '1' (count never reaches 3 before end)
• No separator needed, so output is "123"

Time and Space Complexity

Brute-force Approach:
A brute-force approach might involve repeatedly slicing the string and concatenating with separators, which could take O(k^2) time where k is the number of digits (due to repeated string concatenation).

Optimized Approach:
The optimized solution processes each digit exactly once, so the time complexity is O(k), where k is the number of digits in n. Space complexity is also O(k), since we store the formatted string.

Summary

The "Thousand Separator" problem is a string manipulation task that can be solved efficiently by iterating through the number's digits from right to left, inserting dots after every three digits, and then reversing the result. This approach is both simple and efficient, requiring only a single pass and minimal extra space. It demonstrates careful handling of grouping and formatting, which is a common pattern in software development.