Hiring Workers

In Hiring Worker why does AM>=GM fail?

e.g.
Let the numbers be x1,x2…xn.

Let x1x2…xn =p(given)

X1+x2+x3+…xn=s .

Using am & gm inequality

(X1+x2+…+xn)/n>=(x1x2…xn)^1/n

S/n>=p^(1/n).

S>=n*p^(1/n).

Problem can be reframed as :

Find K numbers such that their LCM is x and their sum is minimum .

Brute-force/dp can be used to find it .(As there are only 8 distinct primes)

3 Likes

Me too thinking about the same.

8 distinct primes how?

The maximum size of x is 1e6 so and multiplying primes more than the first 8 primes itself leads to a larger value than 1e6 , so maximum number of primes will be 8.

I understood this but couldn’t code :frowning:

I guess my solution could have worked if I had atleast thought it this way :frowning:

can we reframe it like this too ?

"Find K numbers such that their product is X and their sum is minimum "

can u please tell the test case for this solution.

Say, you have to find 3 numbers whose LCM is 18 and sum is minimum .

But you, say product is 18 and sum is minimum ,
you find 3 numbers : 3 * 6 * 1 (say) whose product is 18 and sum is 10 . But, that is wrong because LCM is (3,6,1) = 6 ! = 18

2 Likes

That’s where I was wrong , thankyou for clarifying it !