Glowing Bulbs

This approach is straightforward, we will keep a ‘COUNTER’ initialized with 0. Then we iterate over integers starting from 2. For each integer, we will check whether it is multiple of any of the given ‘N’ prime numbers in the list ‘LABELS’ or not.  If it is multiple of any of those prime numbers then we increment the ‘COUNTER’ by ‘1’.  When the value of ‘COUNTER’ becomes ‘K’ then we return the current integer as it will be the integer assigned to the Kth glowing bulb.

Algorithm :

• Initialize an integer variable ‘COUNTER’ := 0.
• Run a loop where ‘i’ starts 1 and in each iteration do the following -:
  • Iterate over the list LABELS, and if for any prime integer ‘p’ in the list LABELS if  i % p = 0, then do COUNTER := COUNTER + 1 and break this inner loop.
  • If COUNTER = ‘K’ then return ‘i’.

We can say, that the integer assigned to the Kth glowing bulb is in the range [2, K * 30]  because LABELS[i] can not be greater than 30 (see constraints), and so this integer cannot be greater than K * LABELS[i] for any valid ‘i’.

Now, by using the inclusion-exclusion principle we can find the number of bulbs having assigned integer at most ‘X’  that will glow when all the given switches are turned ON.

Let this number of bulbs be COUNT, then if there are only two prime numbers p1, p2, in the list LABELS:

Then COUNT  = X/p1 + X/p2 - X/(p1*p2) where, ‘/’ denote floor division.

Similarly for three primes p1, p2, p3 -:

COUNT = X/p1 + X/p2 + X/p3 - X/(p1*p2) - X/(p1*p3) - X/(p2*p3) + X(p1*p2*p3)

We can generalize it for ‘N’ primes in the same way.

We can say, that if for any integer ‘X’ the number of bulbs having assigned integer at most ‘X’  that will glow when all the given switches are turned ON is less than ‘K’  then our answer must be greater than ‘X’ otherwise it will be less than or equal to ‘K’.  This suggests we use binary search in this problem.  We can solve it using binary search as follows.

Algorithm

• Initialize two integer variables ‘START’:= 2 and ‘END’:= K*30.
• Run a while loop till ‘END’ > ‘START’ and in each iteration do the following -:
  • Initialize ‘MID’:= ‘START’ + (‘END’ - ‘START’) / 2.
  • Initialize an integer variable ‘COUNT’:= 0.
  • Now we will count the number of bulbs that have assigned integer at most ‘MID’  that will glow when all the given switches are turned ON using the inclusion-exclusion principle. To do this we run a loop where ‘i’ ranges from 1 to 2 ^ N - 1 and in each iteration we do following -:
    • Initialize integer variable ‘PRODUCT’:= 1 and boolean variable ‘SIGN’:= true
    • Run a loop where ‘j’ ranges from 0 to ‘N’ and if ‘j’th bit is set in ‘i’ then do ‘PRODUCT’:= ‘PRODUCT’ * LABELS[j] and ‘SIGN’:= !SIGN 
    • If ‘SIGN’ = true, then do ‘COUNT’ -= MID/PRODUCT otherwise do COUNT += MID / PRODUCT.
  • If ‘COUNT’>= ‘K’,  then do ‘END’= ‘MID’.
  • Otherwise do ‘START’= ‘MID’ + 1.
• Return ‘START’.