Get Minimum Number Of Bulbs Off
The management team at one of Amazon's warehouse facilities is planning to install a smart lighting system.
A total of n smart bulbs will be installed along a straight line. A smart bulb automatically turns OFF if the sum of the brightness of the bulbs in front of it is greater than its own brightness. The bulbs can be rearranged in any order. The team wants to find out the minimum number of bulbs that will turn OFF across all possible permutations of the sequence of bulbs.
Given an array, brightness, that represents the brightness of the bulbs placed along a straight line, find the minimum number of bulbs that will turn OFF if the bulbs can be rearranged in any order.
Note: All bulbs are turned ON initially. They turn OFF (in order, from left to right) based on the condition mentioned above.
1Example 1
Suppose, n = 5, brightness = [2, 1, 3, 4, 3]
Some of the possible arrangements of bulbs, their final states, and the corresponding number of OFF bulbs are as follows -
Arrangement | Final State | OFF Count
[2, 1, 3, 4, 3] [T, T, T, F, F] = 3
[2, 3, 4, 1, 3] [T, T, T, F, F] = 3
[3, 2, 4, 1, 3] [T, T, T, F, F] = 3
[4, 3, 3, 2, 1] [T, T, F, F, F] = 4
[1, 2, 3, 4, 3] [T, T, T, T, F] = 2
[3, 3, 1, 4, 2] [T, T, T, F, F] = 3
Note: T = ON state, F = OFF state
One of the optimal arrangements is [1, 2, 3, 4, 3]. The minimum number of OFF bulbs in the final state is 2.
One of the optimal arrangements is [1, 2, 3, 4, 3]. The minimum number of OFF bulbs in the final state is 2.
Constraints
Limits and guarantees your solution can rely on.
🍓🍓