algoadvance

Leetcode 1556. Thousand Separator

Problem Statement

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"

Example 3:

Input: n = 123456789
Output: "123.456.789"

Example 4:

Input: n = 0
Output: "0"

Clarifying Questions

  1. Q: Can the input number be negative?
    • A: No, the problem states ‘given an integer n’, and examples are for non-negative integers only.
  2. Q: What is the max value of integer n we need to handle?
    • A: In C++, integer can be very large but we’ll assume it’s within the range of a standard 32-bit integer unless otherwise specified.

Strategy

We will convert the integer n to a string to manipulate its characters easily. Starting from the end of the string, we will insert a dot (‘.’) every three characters. Finally, we will return the modified string.

Code

#include <iostream>
#include <string>
using namespace std;

string thousandSeparator(int n) {
    string numStr = to_string(n);
    string result;
    int len = numStr.length();
    
    for (int i = 0; i < len; ++i) {
        if (i > 0 && (len - i) % 3 == 0) {
            result += '.';
        }
        result += numStr[i];
    }
    
    return result;
}

// Testing the function
int main() {
    int test1 = 987;            // Output: "987"
    int test2 = 1234;           // Output: "1.234"
    int test3 = 123456789;      // Output: "123.456.789"
    int test4 = 0;              // Output: "0"
    
    cout << thousandSeparator(test1) << endl;
    cout << thousandSeparator(test2) << endl;
    cout << thousandSeparator(test3) << endl;
    cout << thousandSeparator(test4) << endl;
    
    return 0;
}

Time Complexity

The time complexity of this solution is O(m), where m is the number of digits in the integer n (i.e., the length of the string representation of n). Inserting characters into a string in C++ which may involve reallocations internally is generally O(n). Since we are only dealing with integers and their string representations efficiently, the overall time complexity remains linear concerning the number of digits (m).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI