LeetCode Thousand Separator Solution

Thousand Separator (LeetCode 1556) asks you to format a number the way many European countries write it, with a dot between every group of three digits. It is an easy problem, but it is a nice exercise in working with string positions from the right-hand end.

Problem

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

Constraints: 0 ≤ n < 2³¹

Input: n = 987          Output: "987"
Input: n = 1234         Output: "1.234"
Input: n = 123456789    Output: "123.456.789"
Input: n = 0            Output: "0"

Approach

The groups of three are counted from the right, not the left. That is why "1234" becomes "1.234" and not "123.4". So turn the number into a string and walk backwards in steps of three:

1. Convert n to a StringBuilder.
2. Start at position length - 3. If that position is greater than 0, insert a dot there.
3. Move three places to the left and repeat until the position reaches 0 or goes below it.

Inserting from the right is important. Each insert shifts everything after it, but because we always move left, the positions we still have to visit are not affected.

Example with n = 123456789. The length is 9. Insert at 6: "123456.789". Insert at 3: "123.456.789". The next position is 0, so we stop. The check i > 0 is what stops a dot appearing at the very start for numbers like 123456.

Solution in Java

class Solution {
    public String thousandSeparator(int n) {
        StringBuilder s = new StringBuilder(String.valueOf(n));
        for (int i = s.length() - 3; i > 0; i -= 3) {
            s.insert(i, ".");
        }
        return s.toString();
    }
}

Complexity

A number below 2³¹ has at most 10 digits, so this is effectively constant time. In general, for a d-digit number, each insert shifts up to d characters and there are about d/3 inserts, so it is O(d²). Building the result from the right into a new string and reversing it at the end brings that down to O(d).

Other ways to do it

• String.format("%,d", n) gives "123,456,789" with commas (in an English locale), so String.format("%,d", n).replace(',', '.') also works. Interviewers usually want the manual version, though.
• In Python the same trick is f"{n:,}".replace(",", ".").
• Indian numbering puts the first separator after three digits and the rest after every two (12,34,56,789). Try changing the loop to do that. It is a good follow-up exercise.

Tip: try to solve the problem yourself before reading the solution. Use the code as a reference to check your approach, and make sure you understand why it works.

More LeetCode solutions All coding problems MCQ practice