Last Updated: 21 Oct, 2021
Sweets and Ants
Easy
Asked in companies
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.
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
Approaches
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.
Approach: First, let’s say we are at ‘ith’ sweet, then the freshness value of a ‘jth’ sweet if ‘j’ <= ‘i’ will be ( N - (i - j)). Now we will use a stack to store the remaining sweets. We will add the sweet id in the stack at each step and then pop the top values till the conditions follow. We can find the current freshness of sweet at the top using the above formula. The solution works because ants always prefer the fresher sweet, and the sweet at the top has maximum freshness while the sweet at the bottom has the least freshness.
Algorithm:
- Create a stack ‘St’.
- Create an array ‘ans’ of length ‘N’ and initialize all its values to 0
- Iterate using a for loop from i = ‘0’ to ‘N’ - 1.
- Append ‘i + 1’ in the stack.
- While ‘St’ is not empty and ‘i + 1 - St.top’ < S[i] .
- Update ans[St.top - 1] to 1
- Pop the top of the stack.
- Print the ‘ans’ array.