Ninja And Candies

Moderate
0/80
Average time to solve is 15m
26 upvotes
Asked in companies
Goldman SachsAmazonApple

Problem statement

Ninja is a boy who lives in ninjaland. Every day, during the morning he gets 1 coin from his mother. He wants to buy exactly ‘N’ candies. Each of the candies cost 2 coins usually and 1 coin if it is on sale. Ninja has to buy exactly K[i] candies of the i-th type(he buys candies in the evening).

Ninjas can buy any(possibly zero) number of candies of any type during any day(if he has enough money to do it). If the candy is on sale he can buy it for 1 coin and otherwise he has to buy it for 2 coins.

There are ‘M’ special offers in the candy shop. The j-th offer (D[j], C[j]) means that candies of the C[j]-th type are on sale during the D[j]-th day.

Ninja wants to buy all candies as soon as possible. Your task is to calculate the minimum day when he can buy all the candies.

Detailed explanation ( Input/output format, Notes, Images )
Input Format 
The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then the test cases follow.

The first line of each test case contains two space separated integers ‘N’ and ‘M’ denoting the total number of types of candies and the number of special offers in the candy shop.

The second line of each test case contains ‘N’ space-separated integers K[i], denoting the number of candies of each type Ninja has to order.

The next M-lines contain two space-separated integers (D[i], C[i]), denoting that the candy of C[i] type is on sale on the D[i]-th day.
Output Format : 
For each query, print the minimum day when the Ninja can order all candies.

Output for each test case will be printed in a new line.
Note: 
You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10
1 <= N, M <= 10^4
0 <= K[i] <= 10^4
1 <= C[i] <= N
1 <= D[i] <= 10^4

Here N denotes the total number of candies and M denotes the total number of special offers.
Here K[i] denotes the number of candies of the i-th type Ninjas has to order.
Here C[i]  and D[i] denote that the candy if the C[i]-th type will be on sale on the D[i]-th day.
Sum of K[i]’s in each test case will be less than 5000.
Sample Input 1 :
2
4 4
1 0 2 0
1 1
1 3
2 1
2 3
3 3
1 1 1
1 1
1 2
1 3
Sample Output 1:
4
5
Explanation of Input 1:
For test case 1, Ninja can buy candies in the following manner-

• Buy candy of type 1 on day 1 for 1 coin.
• Buy candy of type 3 on day 2 for 1 coin.
• Buy candy of type 3 on day 4 for 2 coins.

For test case 2, Ninja can buy candies in the following manner-
• Buy candy of type 1 on day 1 for 1 coin.
• Buy candy of type 2 on day 3 for 2 coins.
• Buy candy of type 3 on day 5 for 2 coins.
Sample Input 2 :
1
5 6
1 2 0 2 0
2 4
3 3
1 5
1 2
1 5
2 3
Sample Output 2:
8
Hint

Can we iterate over days to get our answer?

Approaches (2)
Using Linear Search

We will iterate over all possible days, which will be between 1 to 2*(sum of all K[i]). Let our current day be ‘currDay’. We will check if any valid distribution is possible for the current day.

If we had several days for some type of candies, let's use the last one, it is always not worse than some of the previous days. Then let's iterate over all days from 1 to ‘ansd’ and do the following: 

  • Firstly, let's increase our balance by one coin.
  • Then let's try to order all candy for which the current day is the last sale day (and pay one coin per candy). If we are out of money at some moment then just say that we should order all candy that remains in this sale day during the last day for two coins per candy.
  • It is true because it does not matter which types will remain because this day is the last sale day for all of these types. So, after all, we had some remaining candy that we cannot buy during sales, and the current balance. And the current day is good if the number of such candies multiplied by two is not greater than the remaining balance.

The algorithm will be-

  • We will iterate from 1 to 2*(sum of all K[i]). Let current day be ‘currDay’. We will check if we can buy all candies within ‘currDay’.
  • We will find the last day of sale for all the ‘M’ candies which are less than ‘currDay’ in an array/list ‘last’.
  • For each day ‘i’ which is less than ‘currDay’ we will store all the jobs which have the i-th day as the last day of sale.
  • Let our current money be ‘currMoney’. We copy the contents of array/list ‘K’ in an array/list ‘need’. Now for each day ‘i’ from 1 to ‘currDay’:
    • Increment ‘currMoney’ by 1.
    • For all candies ‘j’, which have the i-th day as the last day of sale:
      • If currMoney >= need[j]:
        • Subtract need[j] from ‘currMoney’.
        • Set need[j] to 0.
      • Else,
        • Subtract ‘currMoney’ from need[j].
        • Set ‘currMoney’ to 0.
  • If 2*(sum of element of array/list ‘need’) is less than equal to ‘currMoney’, we return true. Else, we return false.
Time Complexity

O(sumCandy * sumCandy), where sumCandy is the total number of candy which Ninja has to buy. 

The time complexity due to the linear search will be O(sumCandy). For each check, we are iterating over all days. Thus, the total time complexity will be O(sumCandy * sumCandy).

Space Complexity

O(sumCandy * sumCandy), where sumCandy is the total number of candy which Ninja has to buy. 

The space complexity for each check will be O(sumCandy) due to storing all the jobs which have the i-th day as the last day of sale. As we performing this check for sumCandy times in the worst case, the overall space complexity will be O(sumCandy*sumCandy).

Code Solution
(100% EXP penalty)
Ninja And Candies
Full screen
Console