Just write some cases, for example take initial ON switches=>2,3,5 and check what will be the position "among ON bulbs" of 10th bulb in this case, you will understand how inclusion-exclusion principle is working here. The solution is (binary)searching the first bulb from left such that its position is >=n, which would be at nth position.

Yes you are right this problem need binary search and inclusion-exclusion principle.

let nth glowing light is at position k so we will apply binary search on k to check that whether we get atleast n glowing light till k and this can be done using inclusion exclusion principle.

to check that we don't need to consider all 40 bits because only prime number button can be ON and so consider all 12 prime number less than 40 and find out the number of glowing light till k using inclusion exclusion principle.

Complexity of solution will O(T*log(MAX)*(2^12)) where MAX is maximum value of k that could (37*n)

The problem is essentially this —

You are given $$$k \le 12$$$ prime numbers. Return the $$$n$$$-th multiple.

Let me explain the case when there $$$2$$$ prime numbers. Let us define a function $$$f(n,p_1, p_2)$$$ where $$$f(n,p_1, p_2)$$$ represents the number of multiples of $$$p_1, p_2$$$ till $$$n$$$.

Now, it is easy to see that $$$f(n, p_1, p_2)$$$ is a monotonic function. Given an integer $$$n$$$, it is easy to calculate $$$f(n, p_1, p_2) = n/p_1 + n/p_2 - n/l(p_1, p_2)$$$, where $$$l(p_1, p_2)$$$ represents the LCM of $$$(p_1, p_2)$$$.

The binary search idea is very beautiful because it is difficult for us to answer the question — 'What is the $$$k$$$-th multiple of these numbers ?' but it is easy to answer 'Given an integer $$$n$$$, how many multiples are there till $$$k$$$ ?'

I have written an editorial about the $$$k = 2$$$ case here.

Now, the question is how do we generalise to more than $$$2$$$ integers ? Let us take the example of $$$4$$$ integers

$$$f(n, p_1, p_2, p_3, p_4) = (n/p_1 + n/p_2 + n/p_3 + n/p_4)$$$ $$$- (n/p_1p_2 + n/p_1p_3 + n/p_1p_4 + n/p_2p_3 + n/p_2p_4 + n/p_3p_4)$$$ $$$+ (n/p_1p_2p_3 + n/p_2p_3p_4)$$$ $$$- (n/p_1p_2p_3p_4)$$$

Now, you will notice a general trend emerging. There is a $$$+$$$ sign attached when there are an odd number of integers attached and a $$$-$$$ sign attached where there are an even number of integers attached. If only there was a function which captured this ! But there is, — The Mobius Function !

$$$f(n, p_1, p_2, p_3, p_4) = \sum_{j = 1}^{j = p_1p_2p_3p_4} \mu (j) n/j$$$

The mobius function - Returns $$$0$$$ if the integer is not squarefree. - Returns $$$+1$$$ if there are an odd number of divisors - Returns $$$-1$$$ if there are an even number of divisors

Now, in practical terms, what we need to do in order to find out $$$f(n)$$$ is this — - Create a bitmask of length $$$12$$$. - Each bit corresponds to a different prime number. The first bit to $$$2$$$, second to $$$3$$$, and so on till $$$37$$$. - Go through all $$$2^{12}$$$ bitmasks and process a bitmask only if it contains primes that we are interested in - The parity of the number of bits set will give us the sign - Get the number by multiplying the corresponding integers of each bit and divide $$$n$$$ by this number

Hope it helps