algoadvance

Leetcode 2710. Remove Trailing Zeros From a String

Problem Statement

You are given a string num representing a large integer. The task is to remove all trailing zeros in the string. Return the resulting string.

Example:

Input: num = "1234000"
Output: "1234"

Input: num = "1000"
Output: "1"

Input: num = "0"
Output: "0"

Clarifying Questions

  1. Q: Will the input always be a valid numerical string? A: Yes, it is stated that num represents a large integer.

  2. Q: Can the string have leading zeros? A: The problem does not specifically mention this, but generally, numerical representations do not have leading zeros unless the number is zero itself.

  3. Q: Should the function handle an empty string? A: For this context, it can be assumed the input will not be empty as it represents a large integer.

Strategy

To solve this problem, we’ll start from the end of the string and move backwards, counting and skipping all zeros until we find a non-zero character. We can then return the substring from the start to that point.

Steps:

  1. Traverse the string from the end and find the position of the last non-zero character.
  2. Return the substring from the beginning to this position.

Code

#include <iostream>
#include <string>

std::string removeTrailingZeros(std::string num) {
    int endIdx = num.size() - 1;
    
    // Find the index of the last non-zero character.
    while (endIdx >= 0 && num[endIdx] == '0') {
        endIdx--;
    }
    
    // If endIdx is -1, it means the entire string was zeros, return "0".
    return endIdx == -1 ? "0" : num.substr(0, endIdx + 1);
}

int main() {
    std::string num1 = "1234000";
    std::cout << removeTrailingZeros(num1) << std::endl; // Output: "1234"
    
    std::string num2 = "1000";
    std::cout << removeTrailingZeros(num2) << std::endl; // Output: "1"
    
    std::string num3 = "0";
    std::cout << removeTrailingZeros(num3) << std::endl; // Output: "0"
    
    return 0;
}

Time Complexity

The time complexity of this algorithm is O(n), where n is the length of the input string. This is because, in the worst case, we need to scan the entire string once to find the last non-zero character.

The space complexity is O(1) (excluding the input and output), as we are only using a fixed amount of extra space.

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