can any one help me with this question … it was asked today in gfg hiring contest
question link
2 Likes
We have two cases:
- Even number - has achieved its maximum state, cannot increase further can also decrease by dividing by 2
- Odd number - has achieved its minimum state, cannot decrease further but can be taken to the maximum state by multiplying by 2.
Therefore, you can multiply all odd numbers in the array by 2. Then put the elements in a max_heap priority_queue. After that you can just take the maximum element from the top, get the difference from the minimum element. Pop it and push element/2 again back in the priority_queue. Iterate until you get an odd number or the top element is greater than your lowest number and keep updating your final answer with the difference to get the minimum.
BTW, were you able to solve the question before it, i.e, the Audiophile geek question?
I only know that we have to use combinatorics but couldn’t derive the formula for it.
Sorry to hear that you got this in a hiring contest. This was asked just a couple of weeks ago on leetcode weekly contest (https://leetcode.com/contest/weekly-contest-217). Many of those who attended that contest may have solved this.
Gfg hiring copied literally every problem from either its own platform(lol) or from leetcode. The Audiophile is exact copy of this problem