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 o...read more

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’.

O(1).

We are not using any extra space here.

O(N * (2 ^ N) * log(K)), where N’ denotes the size of the array/list ‘LABELS’ and ‘K’ is the given integer.

We will have log(K) iteration in binary search and in each iteration it takes N * 2 ^ N time to count the number of bulbs less than ‘MID’ that will glow. Thus the overall complexity will be  O(N * (2 ^ N) * log(K)).

/*



    Time Complexity : O(N * (2 ^ N) * log(K))

    Space Complexity : O(1)



    Where 'N' denotes the size of the array/list 'LABELS' and 'K' is the given integer.



*/



import java.util.ArrayList;



public class Solution 

{

    public static long findKthGlowingBulb(ArrayList labels, long k) 

    {

	    // Number of switches.

        int n = labels.size();



        long start = 0, end = k*30;



        // Binary search to find answer.

        while (end > start) 

        {

            long mid = start + (end - start) / 2;

            long count = 0;



            // Using inclsion-exclusion principle to count number of glowing bulbs having

           // assigned integer not more than 'mid'.

           for (int i = 1; i < (1 << n); i++) 

           {

               long product = 1;

               boolean sign = true;

               for (int j = 0; j < n; j++) 

               {

                    if ((i & (1 << j)) > 0) 

                    {

                        product = product * labels.get(j);

                        sign = !sign;

                    }

                }

                if (sign == true) 

                {

                    count -= mid / product;

                }

                else 

                {

                   count += mid / product;

                }

            }

           

            // Answer will be in range [start, mid].

            if (count >= k) 

            {

                end = mid;

            }

        

            // Answer will be in range [mid+1, end].

            else 

            {

               start = mid + 1;

            }

        }



        return start;

	}

}

/*



    Time Complexity : O(N * (2 ^ N) * log(K))

    Space Complexity : O(1)



    Where ‘N’ denotes the size of the array/list ‘LABELS’ and ‘K’ is the given integer.



*/



long long findKthGlowingBulb(vector &labels, long long k) {

    // Number of switches.

    int n = labels.size();



    long long start = 0, end = k*30;



    // Binary search to find answer.

    while (end > start) {

        long long mid = start + (end - start) / 2;

        long long count = 0;



        // Using inclsion-exclusion principle to count number of glowing bulbs having

        // assigned integer not more than 'mid'.

        for (int i = 1; i < (1 << n); i++) {

            long long product = 1;

            bool sign = true;

            for (int j = 0; j < n; j++) {

                if (i & (1 << j)) {

                    product = product * labels[j];

                    sign = !sign;

                }

            }

            if (sign == true) {

                count -= mid / product;

            }

            else {

                count += mid / product;

            }

        }

        // Answer will be in range [start, mid].

        if (count >= k) {

            end = mid;

        }

        // Answer will be in range [mid+1, end].

        else {

            start = mid + 1;

        }

    }



    return start;

}

'''



    Time Complexity : O(N * (2 ^ N) * log(K))

    Space Complexity : O(1)



    Where ‘N’ denotes the size of the array/list ‘LABELS’ and ‘K’ is the given integer.



'''



def findKthGlowingBulb(labels, k):

    # Number of switches.

    n = len(labels)



    start, end = 0, k * 30



    # Binary search to find answer.

    while (end > start):

        mid = start + (end - start) // 2

        count = 0



        # Using inclsion-exclusion principle to count number of glowing bulbs having

        # assigned integer not more than 'mid'.

        for i in range(1, 1 << n):

            product = 1

            sign = True

            for j in range(n):

                if (i & (1 << j)):

                    product = product * labels[j]

                    sign = not sign

        

            if (sign == True):

                count -= mid // product

            else:

                count += mid // product

            

        # Answer will be in range [start, mid].

        if (count >= k):

            end = mid

        # Answer will be in range [mid+1, end].

        else:

            start = mid + 1

        

    return start