PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Setter: Jafar Badour
Tester: Hussain
Editorialist: Taranpreet Singh
DIFFICULTY:
Cakewalk
PREREQUISITES:
None at all (what did you expect?? :D)
PROBLEM:
A bank have a total of K cash. N customers visit bank one day, and request to withdraw A[i] money. We have to tell which customers get money, and which ones doesn’t.
SUPER QUICK EXPLANATION
-
Check customers from front to end, if bank can give cash to customer, Bank gives and reduces its cash balance. That's all.
EXPLANATION
The only thing we need to do is to simulate the customers from front to end, and see if we can satisfy their cash requirement.
Formally, If K \geq A[i] for ith customer, we set K = K-a[i] and append 1 to answer string. Otherwise we append 0 to answer string and move to next customer.
What we are doing here is, that if we can lend cash to ith customer (this occurs when K \geq A[i]), we lend it and reduce bank’s cash balance by A[i], Otherwise we refuse that customer and bank’s cash balance remains unaffected.
This is it. You may feel free to refer Solutions if you wish to.
Time Complexity
Since we iterate over all customers only once, Time complexity is O(N).
AUTHOR’S AND TESTER’S SOLUTIONS:
Setter’s solution
Tester’s solution
Editorialist’s solution
Feel free to Share your approach, If it differs. Suggestions are always welcomed. 