Last Updated: 25 Dec, 2020

Santa Claus and His Magic Bag

Easy

Asked in companies

Solve now

Problem statement

This year Santa Claus got a magic bag for bringing gifts for children. So magical thing about this magic bag is that, whenever the number of gifts inside the bag becomes strictly less than 'K' gifts, it automatically refills back to its full capacity(say its capacity is of 'N' gifts). Now a child can ask for 'M' (some positive integer less than 'N') gifts from Santa. This reduces the number of gifts in the bag by 'M'.

On the occasion of Christmas, when Santa Claus arrived, children of your locality made a queue for taking gifts from Santa Claus. But some greedy kids can ask for more gifts than the current number of gifts in the bag which is regarded as invalid demand and that kid doesn't get any gift.

You are watching this distribution of gifts, and become curious about knowing the number of gifts remaining in Santa's bag after giving gifts to a kid. You get the ordered list of demands of kids as 'DEMANDS', can you tell which are invalid demands and how many gifts left in the bag if the demand is valid?

Note:

1. You can assume Magic Bag is completely filled initially.

2. If the demand by a kid is invalid print -1 which will denote this invalid demand.

Input format:

The first line of the input contains three space-separated integers N, K, and Q, denoting the capacity of Magic Bag, the minimum number of gifts in the bag below which it refills itself, and the size of the demand list.

The next 'Q' lines contain an Integer one per line, denoting the number of gifts demanded by i’th kid, DEMANDS[i].

Output format:

For each test case, print a single line containing a single integer that denotes the number of gifts present after giving gifts to i’th kid. In case of invalid demand from kid print -1.

The output of each test case will be printed in a separate line.

Note:

You don't have to print anything. It has already been taken care of. Just Implement the given function.

Constraints:

1 <= K <= N <= 10 ^ 9
1 <= Q <= 10 ^ 6
1 <= DEMANDS[i] <= 2 ^ 31 

Time Limit: 1 sec.

Solve now

Approaches

01 Approach

Keep the count of the present number of gifts in variable, let it be ‘currentGifts’.
Iterate through the demands (with for loop variable ‘i’).
Check if ‘i’th demand is valid or not.
- For checking demand if valid or not, simply compare demand[i] with currentGifts.
- If currentGifts is greater than or equal to demand[i] then it is valid.
- Else if is invalid.
If ‘i’th operation is valid, then:
- Complete the ‘i’th demand, and take out demand[i] gifts from the magic bag and reduce currentGifts by demand[i].
- If the number of gifts inside the bag becomes strictly less than K, then refilling of the bag takes place and making currentGifts equals to N.
- Finally print the currentGifts.
If ‘i’th operation is not valid, then simply print -1

Solve now