Given a positive number n and a positive number k. How to find the minimum number of sets such that for each set s , the product of all elements in s is less than or equal to k.
And also all the sets should contain only elements from 1 to n (both inclusive).And each number from 1 to n should be in exactly one set.
My approach was to first find the square root of k (let it be t). And then divide the numbers from 1 to n into 2 parts. First part has numbers less or equal to t , second has numbers greater than t and less than equal to n. Then we can say that no two number in the second part can be in the same set , because their product will be more the k. But this does not completely answer the question. How to do it?
You can solve this as a bin packing problem where the $n$ items have weights $\log 1, \dots, \log n$ and each bin has capacity $\log k$.