Sweets and Ants

Easy

0/40

Average time to solve is 15m

Contributed by

29 upvotes

Asked in companies

Problem statement

You like sweets so much that you decided to make sweets at your home, little do you know that ants living in your house love sweets too. There will be ‘T’ times when you decide to make sweets. Each time you will make ‘N’ types of sweets numbered from ‘1’ to ‘N’. Once you cook ‘ith’ sweet it has a freshness value ‘N’ and all the previous sweet’s freshness values decreases by 1. After cooking each sweet, you will store it in the fridge to cool down and leave. The moment you leave the fridge, ants will steal some of the sweets(might be 0 as well). Since they love fresh sweets, they will steal all the sweets with a freshness value greater than ‘N - S[i]’.

After you cooked all the ‘N’ sweets, you went to the fridge and found that some(might be 0 as well) of the sweets were missing. You have to print an array of length ‘N’ containing 1 and 0, where the ‘ith’ value will be 1 if ants stole that sweet else, it will be 0.

Note: In each test case, the first sweet has id ‘1’, the second sweet has id ‘2’ and so on.

Note: Ants will come to steal every time you cook a sweet.

Detailed explanation ( Input/output format, Notes, Images )

Input Format-

First-line contains ‘T’, denoting the number of Test cases.
For each Test case:
The first line contains an integer ‘N’, denoting the number of sweets you will cook.
The second line contains an array ‘S’ of length ‘N’.

Output Format-

For each Test case:
Print an array of length ‘N’ containing 1 and 0, where the ‘ith’ value will be 1 if ants stole the sweet with id ‘i’ else, it will 0.

Constraints -

1<= ‘T’ <= 5
1<= ‘N’ <= 10^5
0<= S[i] <=‘N’  i ∈  (1,N)


Time Limit: 1 sec

Sample Input-1

3
6
0 3 0 0 1 3
10
0 0 0 1 0 5 0 0 0 2
3
0 0 0

Sample Output-1

1 1 0 1 1 1 
0 1 1 1 1 1 0 0 1 1 
0 0 0

Explanation for Sample Input 1:

For test case 1:
    After you cooked the first sweet, ants did not steal any sweet.
    After you cooked the second sweet, ants stole both the sweets.
    After you cooked the third and fourth sweets, ants did not steal any sweets.
    After you cooked the fifth sweet, ants stole the fifth sweet.
    After you cooked the sixth sweet, ants stole the sixth and fourth sweet.
    Hence the third sweet is remaining.
For test case 3:
    Since ants did not steal any sweets, Thus all the sweets were left.

Sample Input -2

Sample Output -2

1 1 1 1 1
1 0 1 1

Hint 1

Hint 2

How can you store the remaining freshness at each step?

Approaches (2)

Approach 1

Approach 2

Brute Force

Approach: We will create an array to store if the ants have stolen the sweet or not and an array to store the freshness value of the sweets.

At each step, we will assign the ‘ith’ sweet a freshness value ‘N’ and then decrease all the previous sweet’s freshness by 1. After that, we will iterate in previous sweets, and if they fulfil the conditions, we will mark them as stolen.

Algorithm:

Create two arrays ‘ans’ and ‘fresh’ of length ‘N’ and initialize their value to 0.
Iterate using a for loop from i = ’0’ to ‘N - 1’.
- Update fresh[i] to N.
- Iterate using a for loop from j = ‘0’ to ‘i - 1’.
  - Decrement fresh[j] by 1.
  - If conditions follows i.e. fresh[j] > N - S[i].
    - Update ans[j] to 1
- If fresh[i] > N - S[i].
  - Update ans[i] to 1.
Print the ‘ans’ array.

Time Complexity

O(N ^ 2).

We are using a ‘for’ loop inside a ‘for’ loop. Hence the overall complexity is O(N ^ 2).

Space Complexity

O(N).

We are creating two arrays of length ‘N’. Hence the overall complexity is O(N).

(100% EXP penalty)

Sweets and Ants

Console