Given two numbers A and B, the task is to remove the trailing zeros present in the sum of the two given numbers using a stack.
Examples:
Input: A = 124, B = 186
Output: 31
Explanation: Sum of A and B is 310. Removing the trailing zeros modifies the sum to 31.Input: A=130246, B= 450164
Output : 58041
Approach: The given problem can be solved using the string and stack data structures. Follow the steps below to solve the problem:
- Calculate A + B and store it in a variable, say N.
- Initialize a stack < char >, say S, to store the digits of N.
- Convert the integer N to string and then push the characters into the stack S.
- Iterate while S is not empty(), If the top element of the stack is ‘0’, then pop it out of the stack. Otherwise, break.
- Initialize a string, say res, to store the resultant string.
- Iterate while S is not empty(), and push all the characters in res and, then pop the top element.
- Reverse the string res and print the res as the answer.
Below is the implementation of the above approach:
C++14
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;Â
// Function to remove trailing// zeros from the sum of two numbersstring removeTrailing(int A, int B){Â Â Â Â // Stores the sum of A and BÂ Â Â Â int N = A + B;Â
    // Stores the digits    stack<int> s;Â
    // Stores the equivalent    // string of integer N    string strsum = to_string(N);Â
    // Traverse the string    for (int i = 0; i < strsum.length(); i++) {Â
        // Push the digit at i        // in the stack        s.push(strsum[i]);    }Â
    // While top element is '0'    while (s.top() == '0')Â
        // Pop the top element        s.pop();Â
    // Stores the resultant number    // without trailing 0's    string res = "";Â
    // While s is not empty    while (!s.empty()) {Â
        // Append top element of S in res        res = res + char(s.top());Â
        // Pop the top element of S        s.pop();    }Â
    // Reverse the string res    reverse(res.begin(), res.end());Â
    return res;}Â
// Driver Codeint main(){    // Input    int A = 130246, B = 450164;Â
    // Function Call    cout << removeTrailing(A, B);    return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.util.*;Â
class GFG{Â
// Function to remove trailing// zeros from the sum of two numbersstatic String removeTrailing(int A, int B){Â Â Â Â Â Â Â Â Â // Stores the sum of A and BÂ Â Â Â int N = A + B;Â
    // Stores the digits    Stack<Character> s = new Stack<Character>();Â
    // Stores the equivalent    // string of integer N    String strsum = Integer.toString(N);Â
    // Traverse the string    for(int i = 0; i < strsum.length(); i++)     {                 // Push the digit at i        // in the stack        s.push(strsum.charAt(i));    }Â
    // While top element is '0'    while (s.peek() == '0')    {                 // Pop the top element        s.pop();    }Â
    // Stores the resultant number    // without trailing 0's    String res = "";Â
    // While s is not empty    while (s.empty() == false)     {                 // Append top element of S in res        res = res + (char)s.peek();Â
        // Pop the top element of S        s.pop();    }Â
    StringBuilder str = new StringBuilder();    str.append(res);Â
    // Reverse the string res    str.reverse();Â
    return str.toString();}Â
// Driver Codepublic static void main (String[] args) {         // Input    int A = 130246, B = 450164;Â
    // Function Call    System.out.println(removeTrailing(A, B));}}Â
// This code is contributed by Dharanendra.L.V. |
Python3
# Python 3 program for the above approachÂ
# Function to remove trailing# zeros from the sum of two numbersdef removeTrailing(A, B):Â
    # Stores the sum of A and B    N = A + BÂ
    # Stores the digits    s = []Â
    # Stores the equivalent    # string of integer N    strsum = str(N)Â
    # Traverse the string    for i in range(len(strsum)):Â
        # Push the digit at i        # in the stack        s.append(strsum[i])Â
    # While top element is '0'    while (s[-1] == '0'):Â
        # Pop the top element        s.pop()Â
    # Stores the resultant number    # without trailing 0's    res = ""Â
    # While s is not empty    while (len(s) != 0):Â
        # Append top element of S in res        res = res + (s[-1])Â
        # Pop the top element of S        s.pop()Â
    # Reverse the string res    res = list(res)    res.reverse()    res = ''.join(res)Â
    return resÂ
Â
# Driver Codeif __name__ == "__main__":Â
    # Input    A = 130246    B = 450164Â
    # Function Call    print(removeTrailing(A, B))Â
    # This code is contributed by ukasp. |
C#
// C# program for the above approachusing System;using System.Collections.Generic;Â
class GFG{     // Function to remove trailing// zeros from the sum of two numbersstatic string removeTrailing(int A, int B){         // Stores the sum of A and B    int N = A + B;      // Stores the digits    Stack<char> s = new Stack<char>();      // Stores the equivalent    // string of integer N    string strsum = N.ToString();      // Traverse the string    for(int i = 0; i < strsum.Length; i++)    {                  // Push the digit at i        // in the stack        s.Push(strsum[i]);    }      // While top element is '0'    while (s.Peek() == '0')    {                  // Pop the top element        s.Pop();    }      // Stores the resultant number    // without trailing 0's    string res = "";      // While s is not empty    while (s.Count != 0)    {                  // Append top element of S in res        res = res + (char)s.Peek();          // Pop the top element of S        s.Pop();    }         char[] str = res.ToCharArray();    Array.Reverse(str);         // Reverse the string res    return new string( str);}  // Driver Codestatic public void Main(){         // Input    int A = 130246, B = 450164;         // Function Call    Console.WriteLine(removeTrailing(A, B));}}Â
// This code is contributed by avanitrachhadiya2155 |
Javascript
<script>Â
        // Javascript program for the above approachÂ
        // Function to remove trailing        // zeros from the sum of two numbers        function removeTrailing(A, B) {Â
            // Stores the sum of A and B            let N = A + B;Â
            // Stores the digits            let s = new Array();Â
            // Stores the equivalent            // string of integer N            let strsum = N.toString();Â
            // Traverse the string            for (let i = 0; i < strsum.length; i++) {Â
                // Push the digit at i                // in the stack                s.push(strsum.charAt(i));            }Â
            // While top element is '0'            while (s[s.length-1] === '0') {Â
                // Pop the top element                s.pop();            }                    // Stores the resultant number            // without trailing 0's            let res = "";Â
            // While s is not empty            while (s.length != 0) {Â
                // Append top element of S in res                res = res.concat(s[s.length-1]);Â
                // Pop the top element of S                s.pop();            }Â
            let str = "";            str = str.concat(res)Â
            // Reverse the string res            str = str.split("").reverse().join("");Â
            return str.toString();        }Â
        // Driver CodeÂ
        // Input        let A = 130246, B = 450164;Â
        // Function Call        document.write(removeTrailing(A, B));Â
        // This code is contributed by Hritik             </script> |
Output:Â
58041
Â
Time Complexity: O(len(A + B))
Auxiliary Space: O(len(A + B))
Â
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
