Problem Brief

Inventory Processes Survival Possibility

FULLTIMEOA

See Amazon online assessment and hiring insights

Within Amazon’s vast fulfillment system, there exist n distinct inventory tasks, each operated by bots[i] bots. These tasks compete, leading to conflict rounds every minute where two random tasks are chosen.

During each conflict:

The task with more bots defeats the other and absorbs all of its bots. 😱

If both tasks have an equal number of bots, one is randomly chosen as the winner and takes over the losing task’s bots. 🏳️

This sequence continues until only one inventory task remains active.

Your objective is to determine which of these tasks have a chance to survive as the final remaining task in at least one possible sequence of events.

Return the 1-based indices of all such tasks, and also please sort it in ascending order 📈.

p.s. if you are applying for a L5 position, you may not want to miss this question..🤧

Gooood news! We might found the shoe selling question: Selling Shoes

The second question in the same batch..Will update once find reliable source..like always~~

1Example 1

Input

n = 5, bots = [1, 6, 2, 7, 2]

Output

[2, 4]

Explanation

The inventory task at position 2 can potentially survive by following these possible clashes (where bots[i] = 0 indicates that its bots have been absorbed by another task): First, the 2nd task defeats the 1st task, acquiring its bots and increasing its count to 6 + 1 = 7. The updated bots array becomes [0, 7, 2, 7, 2]. Next, it eliminates the 3rd task, boosting its total to 7 + 2 = 9. The bots array is now [0, 9, 0, 7, 2]. Afterward, it overpowers the 4th task, raising its bot count to 9 + 7 = 16. The bots array updates to [0, 16, 0, 0, 2]. Finally, it conquers the 5th task, reaching a total of 16 + 2 = 18 bots. The final state is [0, 18, 0, 0, 0]. ~~~~~~~~~😇😇😇😇😇😇😇😇😇😇 Similarly, the inventory task at position 4 can also manage to be the last remaining after these rounds: Initially, the 4th task absorbs the 1st task, collecting its bots to get 7 + 1 = 8. Now the bots array reads [0, 6, 2, 8, 2]. Then, it overtakes the 3rd task, increasing its count to 8 + 2 = 10. The bots array becomes [0, 6, 0, 10, 2]. Following that, it defeats the 2nd task, resulting in a total of 10 + 6 = 16 bots. Updated bots: [0, 0, 0, 16, 2]. Lastly, it overcomes the 5th task, boosting its final count to 16 + 2 = 18. The final bots array is [0, 0, 0, 18, 0]. Therefore, inventory tasks 2 and 4 have the potential to survive until the end in at least one scenario. All other tasks will be eliminated eventually in every possible sequence.

Constraints

Limits and guarantees your solution can rely on.

1 <= n <= 2 * 10^5

1 <= robots[i] <= 10^9