The Remove K Digits problem involves removing K digits from a given number represented as a string to obtain the smallest possible number. This can be efficiently solved using a stack to keep track of the digits and ensure the smallest number is formed.
Consider a number represented by the string:
"1432219"
To remove K digits to form the smallest possible number using a stack, follow these steps:
After performing these steps, the smallest possible number will be formed.
Input: "1432219", K = 3
Output: "1219"
Function remove_k_digits(num, k):
# Initialize an empty stack
stack = []
# Traverse the string
For digit in num:
# Remove larger digits
While stack and k > 0 and stack[-1] > digit:
stack.pop()
k -= 1
# Push current digit
stack.append(digit)
# Handle remaining digits
While k > 0:
stack.pop()
k -= 1
# Build the result and remove leading zeros
result = ''.join(stack).lstrip('0')
# Return the result or '0' if the result is empty
Return result or '0'
class Stack:
def __init__(self):
self.stack = []
def push(self, data):
self.stack.append(data)
def pop(self):
if not self.is_empty():
return self.stack.pop()
return None
def peek(self):
if not self.is_empty():
return self.stack[-1]
return None
def is_empty(self):
return len(self.stack) == 0
def traverse(self):
for item in reversed(self.stack):
print(item, end=" -> ")
print("None")
# Function to remove K digits to form the smallest possible number
def remove_k_digits(num, k):
stack = Stack()
for digit in num:
while not stack.is_empty() and k > 0 and stack.peek() > digit:
stack.pop()
k -= 1
stack.push(digit)
while k > 0:
stack.pop()
k -= 1
result = ''.join(stack.stack).lstrip('0')
return result or '0'
# Example usage:
num = "1432219"
k = 3
print(f"Input number: {num}") # Output: Input number: 1432219
print(f"Number of digits to remove: {k}") # Output: Number of digits to remove: 3
smallest_number = remove_k_digits(num, k)
print(f"Smallest possible number: {smallest_number}") # Output: Smallest possible number: 1219
This Python program defines a stack with methods for pushing, popping, peeking, checking if the stack is empty, and traversing the stack. The remove_k_digits function uses the stack to remove K digits from the input number to form the smallest possible number by processing each digit and updating the stack accordingly.