Thousand Separator

Easy

#1432Time: O(L), where L is the number of digits in `n`. Converting the integer to a string takes O(L). The loop iterates L times, and operations inside (appending to `StringBuilder`) are amortized O(1). The final reversal also takes O(L).Space: O(L), where L is the number of digits in `n`. The `StringBuilder` requires space proportional to the number of digits plus the separators.

Data structures

String

Prompt

Given an integer n, add a dot (".") as the thousands separator and return it in string format.

Example 1:

Input: n = 987
Output: "987"

Example 2:

Input: n = 1234
Output: "1.234"

Constraints:

0 <= n <= 2³¹ - 1

Approaches

2 approaches with complexity analysis and trade-offs.

This is a very intuitive approach. We first convert the number to a string. Then, we iterate through this string from right to left, building a new string. We keep a counter to track digits, and every three digits, we add a dot. Since we build the result string in reverse order (from the least significant digit to the most significant), we need to reverse it at the end to get the final correct format.

Algorithm

Convert the input integer n to its string representation, let's call it s.
If the length of s is less than or equal to 3, no separator is needed. Return s directly.
Initialize a StringBuilder to construct the result.
Initialize a counter, digitCount, to 0.
Loop through the string s from the last character to the first (index s.length() - 1 down to 0).
Inside the loop, append the current character to the StringBuilder.
Increment digitCount.
Check if digitCount is 3 and if we are not at the very beginning of the string (i.e., the loop index is not 0). If both conditions are true, append a . separator to the StringBuilder and reset digitCount to 0.
After the loop completes, the StringBuilder holds the formatted string but in reverse order.
Call the reverse() method on the StringBuilder and then convert it to a string to get the final answer.

Walkthrough

This approach works by processing the number's string representation from right to left, which is the natural way to group digits into thousands. A StringBuilder is used for efficient string construction.

1class Solution {2    public String thousandSeparator(int n) {3        String s = Integer.toString(n);4        if (s.length() <= 3) {5            return s;6        }7        8        StringBuilder resultBuilder = new StringBuilder();9        int count = 0;10        for (int i = s.length() - 1; i >= 0; i--) {11            resultBuilder.append(s.charAt(i));12            count++;13            // Add a dot after every 3 digits, but not at the very beginning14            if (count % 3 == 0 && i > 0) {15                resultBuilder.append('.');16            }17        }18        19        // The string was built backwards, so we need to reverse it20        return resultBuilder.reverse().toString();21    }22}

Complexity

Time

O(L), where L is the number of digits in `n`. Converting the integer to a string takes O(L). The loop iterates L times, and operations inside (appending to `StringBuilder`) are amortized O(1). The final reversal also takes O(L).

Space

O(L), where L is the number of digits in `n`. The `StringBuilder` requires space proportional to the number of digits plus the separators.

Trade-offs

Pros

The logic is simple and follows a natural way of thinking about the problem (grouping from the right).
Easy to implement correctly.

Cons

Requires a final reversal step, which adds an extra pass over the constructed string.

This approach is a slight optimization over the previous one. It avoids the final reversal by first calculating the length of the initial group of digits (the ones before the first separator) and then appending the remaining groups of three, each preceded by a dot. This builds the string in the correct order from left to right.

Algorithm

Convert the integer n to its string representation, s.
Get the length of the string, len. If len <= 3, return s.
Calculate the length of the first group of digits. This is len % 3. If len is a multiple of 3, the first group has 3 digits; otherwise, it has len % 3 digits. Let's call this firstGroupLen.
Initialize a StringBuilder.
Append the first group of digits (from index 0 to firstGroupLen) from s to the StringBuilder.
Loop from firstGroupLen to the end of the string s, incrementing the index by 3 in each step.
In each iteration, append a . separator to the StringBuilder.
Then, append the next group of 3 digits from s.
After the loop, convert the StringBuilder to a string and return it.

Walkthrough

By pre-calculating the length of the first segment of numbers, we can construct the formatted string from left to right, eliminating the need for a final reversal step. This makes the process more direct.

1class Solution {2    public String thousandSeparator(int n) {3        String s = Integer.toString(n);4        int len = s.length();5        if (len <= 3) {6            return s;7        }8        9        StringBuilder sb = new StringBuilder();10        int firstGroupLen = len % 3;11        if (firstGroupLen == 0) {12            // If length is a multiple of 3, the first group has 3 digits13            firstGroupLen = 3;14        }15        16        // Append the first group17        sb.append(s.substring(0, firstGroupLen));18        19        // Append the remaining groups20        for (int i = firstGroupLen; i < len; i += 3) {21            sb.append('.');22            sb.append(s.substring(i, i + 3));23        }24        25        return sb.toString();26    }27}

Complexity

Time

O(L), where L is the number of digits. String conversion is O(L). The loop runs approximately L/3 times. Inside the loop, `substring` and `append` operations contribute to an overall linear time complexity.

Space

O(L), where L is the number of digits. The `StringBuilder` stores the result, which has a length proportional to L.

Trade-offs

Pros

Builds the string in the correct order, avoiding the need for a final reversal.
Potentially slightly more performant than the reversal approach due to fewer overall operations.

Cons

The logic for determining the length of the first group adds a small amount of complexity compared to the straightforward right-to-left iteration.

Solutions

Solution

1class Solution {2public3  String thousandSeparator(int n) {4    int cnt = 0;5    StringBuilder ans = new StringBuilder();6    while (true) {7      int v = n % 10;8      n /= 10;9      ans.append(v);10      ++cnt;11      if (n == 0) {12        break;13      }14      if (cnt == 3) {15        ans.append('.');16        cnt = 0;17      }18    }19    return ans.reverse().toString();20  }21}

1class Solution {2public:3  string thousandSeparator(int n) {4    int cnt = 0;5    string ans;6    while (1) {7      int v = n % 10;8      n /= 10;9      ans += to_string(v);10      if (n == 0)11        break;12      if (++cnt == 3) {13        ans += '.';14        cnt = 0;15      }16    }17    reverse(ans.begin(), ans.end());18    return ans;19  }20};

1class Solution:2    def thousandSeparator(self, n: int) -> str: cnt = 0 ans = [] while 1: n, v = divmod(n, 10) ans . append(str(v)) cnt += 1 if n == 0: break if cnt == 3: ans . append('.') cnt = 0 return '' . join(ans[:: - 1])

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem