Ninja And Candies
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.

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

Question

Ninja And Candies

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.

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.

Accepted Answer

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.

Space Complexity: OtherExplanation:

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).

Time Complexity: OtherExplanation:

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).

Java (SE 1.8)

/*

	Time complexity: O(sumCandy * sumCandy)

	Space complexity: O(sumCandy * sumCandy)

	

	where sumCandy is the total number of candy which Ninja has to buy. 

*/



import java.util.ArrayList;



public class Solution {

    public static boolean isPossible(int currDay, ArrayList days, ArrayList candies, int n, int m,

            ArrayList k) {

        // Computing the last day of sale for each candies

        ArrayList last = new ArrayList<>();



        for (int i = 0; i < n + 1; i++) {

            last.add(-1);

        }



        for (int i = 0; i < m; ++i) {

            if (days.get(i) <= currDay) {

                last.set(candies.get(i), Math.max(days.get(i), last.get(candies.get(i))));

            }

        }



        ArrayList> lastDay = new ArrayList<>();

        for (int i = 0; i < currDay + 1; i++) {

            lastDay.add(new ArrayList());

        }



        /*

         * For each day we are storing in a list all the candies which have the i-th day

         * as the last day of sale

         */

        for (int i = 0; i < n; ++i) {

            if (last.get(i + 1) != -1) {

                lastDay.get(last.get(i + 1)).add(i);

            }

        }



        ArrayList need = new ArrayList<>(k);



        int currMoney = 0;



        for (int i = 1; i <= currDay; ++i) {

            currMoney++;



            for (int j = 0; j < lastDay.get(i).size(); j++) {

                if (currMoney >= need.get(lastDay.get(i).get(j))) {

                    currMoney -= need.get(lastDay.get(i).get(j));

                    need.set(lastDay.get(i).get(j), 0);

                } else {

                    need.set(lastDay.get(i).get(j), need.get(lastDay.get(i).get(j)) - currMoney);

                    currMoney = 0;

                    break;

                }

            }

        }



        int sum = 0;



        for (int i = 0; i < n; i++) {

            sum += need.get(i);

        }



        return ((sum * 2) <= currMoney);

    }



    public static int minimumDays(ArrayList days, ArrayList candies, ArrayList k, int n,

            int m) {

        int high = 0;



        for (int i = 0; i < n; i++) {

            high += k.get(i);

        }

        high *= 2;



        if (high == 0) {

            return 0;

        }



        int low = 1;



        for (int i = low; i <= high; i++) {

            if (isPossible(i, days, candies, n, m, k)) {

                return i;

            }

        }

        return -1;



    }

}

Python (3.5)

'''

	Time complexity: O(sumCandy * sumCandy)

	Space complexity: O(sumCandy * sumCandy)

	

	where sumCandy is the total number of candy which Ninja has to buy. 

'''





def isPossible(currDay, days, candies, n, m, k):



    # Computing the last day of sale for each candies

    last = [-1 for i in range(n + 1)]



    for i in range(m):

        if (days[i] <= currDay):

            last[candies[i]] = max(last[candies[i]], days[i])



    lastDay = [[] for i in range(currDay + 1)]



    '''

		For each day we are storing in a list all the candies

		which have the i-th day as the last day of sale

	'''

    for i in range(n):

        if (last[i+1] != -1):

            lastDay[last[i+1]].append(i)



    need = list(k)



    currMoney = 0



    for i in range(1, currDay + 1):

        currMoney += 1



        for j in range(len(lastDay[i])):

            if (currMoney >= need[lastDay[i][j]]):

                currMoney -= need[lastDay[i][j]]

                need[lastDay[i][j]] = 0



            else:

                need[lastDay[i][j]] -= currMoney

                currMoney = 0

                break



    sum = 0



    for i in range(n):

        sum += need[i]



    return ((sum * 2) <= currMoney)





def minimumDays(days, candies, k, n, m):



    high = 0



    for i in range(n):

        high += k[i]



    high *= 2



    if(high == 0):

        return 0



    low = 1



    for i in range(low, high + 1):

        if(isPossible(i, days, candies, n, m, k)):

            return i

C++ (g++ 5.4)

/*
	Time complexity: O(sumCandy * sumCandy)
	Space complexity: O(sumCandy * sumCandy)
	
	where sumCandy is the total number of candy which Ninja has to buy. 
*/

bool isPossible(int currDay, vector& days, vector& candies, int n, int m, vector& k)
{
	// Computing the last day of sale for each candies
	vector last(n + 1, -1);
	for(int i = 0; i < m; ++i) 
	{
		if (days[i] <= currDay) 
		{
			last[candies[i]] = max(last[candies[i]], days[i]);
		}
	}

	vector> lastDay(currDay +1);

	/*
		For each day we are storing in a list all the candies
		which have the i-th day as the last day of sale
	*/  
	for(int i = 0; i < n; ++i) 
	{
		if (last[i+1] != -1) 
		{
			lastDay[last[i+1]].push_back(i);
		}
	}

	vector need = k;

	int currMoney = 0;

	for(int i = 1; i <= currDay; ++i) 
	{
		currMoney++;

		for(int j = 0; j < lastDay[i].size(); j++) 
		{
			if (currMoney >= need[lastDay[i][j]]) 
			{
				currMoney -= need[lastDay[i][j]];
				need[lastDay[i][j]] = 0;
			} 
			else 
			{
				need[lastDay[i][j]] -= currMoney;
				currMoney = 0;
				break;
			}
		}
	}

	int sum = 0;

	for(int i = 0; i < n; i++)
	{
		sum += need[i];
	}

	return ((sum * 2) <= currMoney);
}

int minimumDays(vector& days, vector& candies, vector& k, int n, int m)
{
	int high=0;

	for(int i = 0; i < n; i++)
	{
		high += k[i];
	}

	high*=2;

	if(high == 0)
	{
		return 0;
	}

	int low=1;

	for(int i = low; i <= high; i++)
	{
		if(isPossible(i, days, candies, n, m, k))
		{
			return i;
		}
	}

}

Accepted Answer

Using Binary Search

To solve this problem, we can use binary search over the answer. The key observations are-

If we can buy every candy in ‘totDays’ days, then we can also buy it in days D > totDays.
Similarly, If we can not buy every candy in ‘totDays’ days, then we also cannot buy it in days D < totDays.

Both of these observations are key attributes of a Binary Search algorithm with in the range [1, 2* (sum of all K[i])] .

The complete algorithm will be-

Now we will binary search over the answer and for each ‘mid’ we can check if we can buy all candies in ‘mid’ days
If we can buy every candy in ‘mid’ days, then set ‘high’ to ‘mid’ - 1. Else set ‘low’ to ‘mid’ + 1.
We finally return (‘high’ + 1) as our answer.

Space Complexity: OtherExplanation:

O(sumCandy * log(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 log(sumCandy) times in the worst case, the overall space complexity will be O(sumCandy*sumCandy).

Time Complexity: OtherExplanation:

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

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

Java (SE 1.8)

/*

	Time complexity: O(sumCandy * log(sumCandy))

	Space complexity: O(sumCandy * log(sumCandy))

	

	where sumCandy is the total number of candy which Ninja has to buy. 

*/



import java.util.ArrayList;



public class Solution {

    public static boolean isPossible(int currDay, ArrayList days, ArrayList candies, int n, int m,

            ArrayList k) {

        // Computing the last day of sale for each candies

        ArrayList last = new ArrayList<>();



        for (int i = 0; i < n + 1; i++) {

            last.add(-1);

        }



        for (int i = 0; i < m; ++i) {

            if (days.get(i) <= currDay) {

                last.set(candies.get(i), Math.max(days.get(i), last.get(candies.get(i))));

            }

        }



        ArrayList> lastDay = new ArrayList<>();

        for (int i = 0; i < currDay + 1; i++) {

            lastDay.add(new ArrayList());

        }



        /*

         * For each day we are storing in a list all the candies which have the i-th day

         * as the last day of sale

         */

        for (int i = 0; i < n; ++i) {

            if (last.get(i + 1) != -1) {

                lastDay.get(last.get(i + 1)).add(i);

            }

        }



        ArrayList need = new ArrayList<>(k);



        int currMoney = 0;



        for (int i = 1; i <= currDay; ++i) {

            currMoney++;



            for (int j = 0; j < lastDay.get(i).size(); j++) {

                if (currMoney >= need.get(lastDay.get(i).get(j))) {

                    currMoney -= need.get(lastDay.get(i).get(j));

                    need.set(lastDay.get(i).get(j), 0);

                } else {

                    need.set(lastDay.get(i).get(j), need.get(lastDay.get(i).get(j)) - currMoney);

                    currMoney = 0;

                    break;

                }

            }

        }



        int sum = 0;



        for (int i = 0; i < n; i++) {

            sum += need.get(i);

        }



        return ((sum * 2) <= currMoney);

    }



    public static int minimumDays(ArrayList days, ArrayList candies, ArrayList k, int n,

            int m) {

        int high = 0;



        for (int i = 0; i < n; i++) {

            high += k.get(i);

        }



        high *= 2;



        if (high == 0) {

            return 0;

        }



        int low = 1;



        while (low <= high) {

            int mid = (low + high) / 2;



            if (isPossible(mid, days, candies, n, m, k) == true) {

                high = mid - 1;

            } else {

                low = mid + 1;

            }

        }



        return high + 1;

    }

}

Python (3.5)

'''

	Time complexity: O(sumCandy * log(sumCandy))

	Space complexity: O(sumCandy * log(sumCandy))



	where sumCandy is the total number of candy which Ninja has to buy.

'''





def isPossible(currDay, days, candies, n, m, k):



    # Computing the last day of sale for each candies

    last = [-1 for i in range(n + 1)]



    for i in range(m):

        if (days[i] <= currDay):

            last[candies[i]] = max(last[candies[i]], days[i])



    lastDay = [[] for i in range(currDay + 1)]



    '''

		For each day we are storing in a list all the candies

		which have the i-th day as the last day of sale

	'''

    for i in range(n):

        if (last[i+1] != -1):

            lastDay[last[i+1]].append(i)



    need = list(k)



    currMoney = 0



    for i in range(1, currDay + 1):

        currMoney += 1



        for j in range(len(lastDay[i])):

            if (currMoney >= need[lastDay[i][j]]):

                currMoney -= need[lastDay[i][j]]

                need[lastDay[i][j]] = 0



            else:

                need[lastDay[i][j]] -= currMoney

                currMoney = 0

                break



    sum = 0



    for i in range(n):

        sum += need[i]



    return ((sum * 2) <= currMoney)





def minimumDays(days, candies, k, n, m):



    high = 0



    for i in range(n):

        high += k[i]



    high *= 2



    if(high == 0):

        return 0



    low = 1



    while(low <= high):



        mid = (low + high) // 2



        if(isPossible(mid, days, candies, n, m, k)):

            high = mid - 1



        else:

            low = mid + 1



    return high + 1

C++ (g++ 5.4)

/*
	Time complexity: O(sumCandy * log(sumCandy))
	Space complexity: O(sumCandy * log(sumCandy))
	
	where sumCandy is the total number of candy which Ninja has to buy. 
*/

bool isPossible(int currDay, vector& days, vector& candies, int n, int m, vector& k)
{
	// Computing the last day of sale for each candies
	vector last(n + 1, -1);
	for(int i = 0; i < m; ++i) 
	{
		if (days[i] <= currDay) 
		{
			last[candies[i]] = max(last[candies[i]], days[i]);
		}
	}

	vector> lastDay(currDay +1);

	/*
		For each day we are storing in a list all the candies
		which have the i-th day as the last day of sale
	*/  
	for(int i = 0; i < n; ++i) 
	{
		if (last[i+1] != -1) 
		{
			lastDay[last[i+1]].push_back(i);
		}
	}

	vector need = k;

	int currMoney = 0;

	for(int i = 1; i <= currDay; ++i) 
	{
		currMoney++;

		for(int j = 0; j < lastDay[i].size(); j++) 
		{
			if (currMoney >= need[lastDay[i][j]]) 
			{
				currMoney -= need[lastDay[i][j]];
				need[lastDay[i][j]] = 0;
			} 
			else 
			{
				need[lastDay[i][j]] -= currMoney;
				currMoney = 0;
				break;
			}
		}
	}

	int sum = 0;

	for(int i = 0; i < n; i++)
	{
		sum += need[i];
	}

	return ((sum * 2) <= currMoney);
}

int minimumDays(vector& days, vector& candies, vector& k, int n, int m)
{
	int high=0;

	for(int i = 0; i < n; i++)
	{
		high += k[i];
	}

	high*=2;

	if(high == 0)
	{
		return 0;
	}

	int low=1;

	while(low <= high)
	{
		int mid = (low + high) / 2;

		if(isPossible(mid, days, candies, n, m, k))
		{
			high = mid - 1;
		} 
		else
		{
			low = mid + 1;
		}
	}

	return high + 1;

}

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.

Input Format

Output Format :

Note:

Constraints:

Top Accenture Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Accenture Software Developer