Thousand Separator Leetcode Solution

Problem Statement

In this problem, we are given a non-negative integer. We have to convert the integer in a such a format, in which there will be some dots which separates all thousands, i.e. there are dots after each 3 places from right.

Example

#1

n = 987

"987"

#2

n = 123456789

"123.456.789"

Explanation:

The number is 123456789. The rightmost dot will be 3 places from right. So, seeing from right, we will leave 9,8 and 7 behind and put a dot between 6 and 7. Then after leaving 6,5 and 4 behind, we will put a dot between 3 and 4.
Now leaving 3,2 and 1 behind, we would place a dot only if there would be more number on left because . should be between two numbers according to the question.
Thus we will not place any dot.

Approach

First of all, we are converting the number into string (let str). Then we are traversing the string str from right. We are using a for loop for this. In each loop we are inserting its three digits followed by a dot.
But after each digit insertion, we will check if we have reached out of the left bound of the str. If yes, then we will break the loop. Otherwise, we will keep inserting the 3 digits and then 1 dot.

Note that the 3rd checking to insert a dot is the crucial one, which will be used in scenarios like 123 or 123.456 or 123.456.789 where we don’t need to insert a dot before leftmost digit.
Because we are inserting the characters from right to left thus our created string needs to be reversed to get the final answer. Thus, after reversing the string, return it.

Implementation

C++ Program for Thousand Separator Leetcode Solution

#include <bits/stdc++.h> 
using namespace std;
string thousandSeparator(int n) {
    string str=to_string(n);
    stringstream ss;
    for(int i=str.length()-1;i>=0;){
        ss<<str[i];//inserting 1st digit
        i--;
        if(i==-1)break;//checking if we are out of left bound
        ss<<str[i];//inserting 2nd digit
        i--;
        if(i==-1)break;//checking if we are out of left bound
        ss<<str[i];//inserting 3rd digit
        i--;
        if(i==-1)break;//checking if we are out of left bound
        ss<<".";//after 3 digits insertion, finally inserting a dot "."
    }
    str= ss.str();
    reverse(str.begin(),str.end());//reversing the final string
    return str;
}

int main()
{
    cout << thousandSeparator(123456789);
}

123.456.789

Java Program for Thousand Separator Leetcode Solution

import java.util.*;
import java.lang.*;

class Solution
{  
    public static  String thousandSeparator(int n) 
    {
        String str=n+"";
        StringBuilder sb=new StringBuilder();
        for(int i=str.length()-1;i>=0;){
            sb.append(str.charAt(i));//inserting 1st digit
            i--;
            if(i==-1)break;//checking if we are out of left bound
            sb.append(str.charAt(i));//inserting 2nd digit
            i--;
            if(i==-1)break;//checking if we are out of left bound
            sb.append(str.charAt(i));//inserting 3rd digit
            i--;
            if(i==-1)break;//checking if we are out of left bound
            sb.append(".");//after 3 digits insertion, finally inserting a dot "."
        }
        return sb.reverse().toString();//reverse and return the final string
    }
    
    public static void main(String args[])
    {
        System.out.println(thousandSeparator(123456789));
    }
}

123.456.789

Complexity Analysis for Thousand Separator Leetcode Solution

Time Complexity

O(len) : we are traversing the given number from right digit to left thus the time Complexity will be O(len) where len is the number of digits in the given number.

Space Complexity 

O(len) : we have used a stringbuilder in java and stringstream in c++ thus using a extra space makes the space complexity O(len).