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!
