Santa Claus and His Magic Bag

Easy
0/40
Average time to solve is 10m
profile
Contributed by
15 upvotes
Asked in companies
Disney + HotstarVisaPhysicsWallah

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.
Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1:
10 4 3
4
2
2
Sample Output 1:
6
4
10
Explanation for sample input 1:
After the 1st demand, Bag contains 10 - 4 = 6 gifts.
After the 2nd demand, Bag contains 6 - 2 = 4 gifts.
After the 3rd operation, Bag contains 4 - 2 = 2 gifts, but now the number of gifts in the bag is less than K, hence magic happens and bag refills back to N gifts.
Sample Input 2:
7 6 2
3
8
Sample Output 2:
7
-1
Explanation for sample input 2:
After the 1st operation, Bag contains 7 - 3 = 4 gifts which is less than K(which is 6), hence Bag refills and contains 7 gifts.
After the 2nd operation, Bag contains 7 gifts, but demand is of 8 gifts from the kid, which is impossible to be fulfilled, hence this demand is invalid.
Hint

Can you keep a count of the previous demands to check the gifts left?

Approaches (1)
Optimal solution
  • 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
Time Complexity

O(Q), where ‘Q’ is the number of demands given in the list.

 

As we just need to go through all the demands once, do some constant time operations, hence we need to do operations of the order of O(Q).

Space Complexity

O(1).

 

Since we are using constant extra space.

Code Solution
(100% EXP penalty)
Santa Claus and His Magic Bag
Full screen
Console