Leetcode – Thousand Separator Solution

Formatting numbers for easier readability is a common task in both software development and data science. The “Thousand Separator” problem on Leetcode provides an excellent opportunity to explore this task from an algorithmic perspective. In this article, we’ll delve deep into various approaches to solve this problem in Python, evaluating them based on their time and space complexities.

Problem Statement

The problem asks us to format a given integer n using a “Thousand Separator.” Specifically, you have to insert a period separator every three digits from right to left. Additionally, you don’t need to add extra leading zeroes before the first group of three digits.

Examples:

1. Input: n = 987 Output: "987"
2. Input: n = 1234 Output: "1.234"
3. Input: n = 123456789 Output: "123.456.789"

Brute-Force Approach: String Manipulation

Algorithm:

1. Convert the integer to its string representation.
2. Reverse the string.
3. Insert a period after every third digit.
4. Reverse the string back to the original order.

Here’s the Python code for the brute-force approach:

def thousandSeparator(n):
    n_str = str(n)[::-1]
    res = []
    for i, digit in enumerate(n_str):
        if i % 3 == 0 and i != 0:
            res.append('.')
        res.append(digit)
    return ''.join(res)[::-1]

Time Complexity:

The time complexity is O(d), where d is the number of digits in n.

Space Complexity:

The space complexity is O(d) as well, due to the extra string that we create for storing the result.

Optimized Approach: Mathematical Manipulation

Algorithm:

1. Start with an empty result string and a counter set to zero.
2. While the number is not zero, do the following:
   • Take the remainder of the number when divided by 10 and append it to the result string.
   • Increment the counter.
   • If the counter is 3, append a period to the result string and reset the counter to zero.
   • Divide the number by 10.

Here’s the Python code for the optimized approach:

def thousandSeparator(n):
    if n == 0:
        return "0"
        
    res = []
    count = 0
    while n:
        n, remainder = divmod(n, 10)
        res.append(str(remainder))
        count += 1
        if count == 3 and n:
            res.append('.')
            count = 0
    return ''.join(res[::-1])

Time Complexity:

The time complexity remains O(d), where d is the number of digits in n.

Space Complexity:

The space complexity is also O(d) due to the extra space used for the result string.

Comparison of Approaches

Conclusion

The “Thousand Separator” problem serves as an excellent example to illustrate the difference between solving a problem and solving it efficiently. While both the brute-force and optimized methods have the same time and space complexity, the optimized approach is preferable because it doesn’t require reversing the string twice. This can make a noticeable impact in terms of execution speed.