algoadvance

Leetcode 2710. Remove Trailing Zeros From a String

Problem Statement

You are given a string num representing a large integer. You need to return the string but with all trailing zeros removed.

Clarifying Questions

  1. What is the maximum length of the string num?
    • Assume the length of the string can be up to 100,000 characters.
  2. Will the string always represent a valid integer (i.e., no leading zeros except for the number “0”)?
    • Yes, the string represents a valid integer.
  3. Is the string guaranteed to contain only digits?
    • Yes, the string will contain only digits (0-9).
  4. What should we return if the string contains only zeros (e.g., "0000")?
    • The output should be "0" in this case.

Strategy

To remove the trailing zeros from the string:

  1. We can iterate from the end of the string until a non-zero character is found.
  2. Use the substring method to get the portion of the string without trailing zeros.
  3. Special case: If the string is completely made up of zeros, return "0".

Code

Here is the Java code to achieve the solution:

public class Solution {
    public String removeTrailingZeros(String num) {
        // Get the length of the string
        int length = num.length();
        
        // Traverse from the end of the string until first non-zero character is found
        int i = length - 1;
        while (i >= 0 && num.charAt(i) == '0') {
            i--;
        }
        
        // If all characters are zeros, return "0"
        if (i == -1) {
            return "0";
        }
        
        // Return substring from 0 to (i + 1)
        return num.substring(0, i + 1);
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        
        // Test cases
        System.out.println(sol.removeTrailingZeros("12345000")); // Output: "12345"
        System.out.println(sol.removeTrailingZeros("1000")); // Output: "1"
        System.out.println(sol.removeTrailingZeros("0000")); // Output: "0"
        System.out.println(sol.removeTrailingZeros("370")); // Output: "37"
    }
}

Time Complexity

The time complexity of this solution is O(n) where n is the length of the string. This is because in the worst case, we need to check each character of the string once from the end of the string towards the beginning. The substring operation also operates in O(n) in the worst case, but since it’s implemented using a reference to the original array in Java, it is very efficient.

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