PROBLEM LINK:
Author: Drishti Sharma
Tester: Shivani Srivastava
Editorialist: Kaushambi Gujral
DIFFICULTY:
EASY
PREREQUISITES:
Stack
PROBLEM:
Considering that one food package can feed two houses, and given the way each package is dropped, you have to tell whether or not each house is fed.
Only the next two houses from the position where the package is dropped can feed on that package.
Note that, the basic motive is to feed all the houses.
QUICK EXPLANATION:
Use a stack. For every ‘0’, push it in the stack. For each ‘*’, pop two elements out of the stack.
EXPLANATION:
The problem can easily be solved using the concept of a stack. Let us take a stack that accepts char type of input. We will feed out entire string to the stack.
If the character is a ‘0’, it means that it is an indication of the presence of a house. We will push this element into the stack. We know that each package can feed 2 homes.
So, if a ‘*’ occurs, it indicates a dropped package for which we will pop(feed) 2 elements(houses/‘0’).
In the end, simply check if your stack is empty or not. If empty, it means that all the houses were fed. Otherwise, they weren’t.
AUTHOR’S AND TESTER’S SOLUTIONS:
The solution can be found here.