FastPrep
Problem · Sorting

Get Minimum Number Of Bulbs Off

Learn this problem
● MediumAmazonFULLTIMEOA
See Amazon hiring insights

Problem statement

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.

Function

getMinimumNumberOfBulbsOff(brightness: int[]) → int

Examples

Example 1

brightness = [2, 1, 3, 4, 3]return = 2

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

🍓🍓

More Amazon problems

drafts saved locally
public int getMinimumNumberOfBulbsOff(int[] brightness) {
  // write your code here
}
brightness[2, 1, 3, 4, 3]
expected2
checking account