You are given an array consisting of N elements. You can perform two operations any no. of times. 1. Make any even element E = E/2. and 2. Make any odd element E = 2E.
You have to minimize the maximum absolute difference between any two elements
For ex- N=2 {1,2}
We can make 2--> 2/2 = 1 Thus answer = 0
What constraints for N?
100 test cases and 50000 maximum no of elements
for each N there are maximum log2(N)+1 number possible.insert it in a set and keep track of minimum and maximum
Can you please, elaborate with some pseudo code.
At least wait for the contest to be over before asking the solution.
I thought everybody would have different problems in their set. It was a 1.5 hour test which I have already submitted.
But where is the contest?
It is the hackerearth problem setting contest.
Can someone help me with the approach to this problem?
Every no. has 2 states, odd or even. Let's make all no.s odd. Sort the array. Now you can clearly see that the ans would be minimum if we make first few elements of the array even and others as it is. You can check for each case.
can u plz send me the code i try but i got wrong ans it would be helpful
I just realized I was wrong in my approach. I wonder why I have upvotes lol. A number can be divided by two multiple times. For example 8 has 4 possible states {8,4,2,1}, So only 2 states thing was wrong. Every number can be be divided by 2, 0 to $$$log(n)$$$ times.
There must be some solution of this using set/multiset or an appropriate data structure. But without them it can also be solved.
Let's say we are given array a[n]. We will first make all the odd numbers even by multiplying by 2. Now, we will never multiply and only divide by 2 , all numbers are their highest states. Let's find minimum of the array. Let us represent it by min. For all numbers other than min, if they are even and dividing them by 2 won't change the min, we should divide them then. Because for the fixed min, it can only decrease max. Once we do this process, let's sort the array in descending order.
Let's have 2 pointers mx and mn, representing indexes of max and min element respectively. Initially mx=0 and mn=n-1, So, now we will iterate cyclically in the array from i=0 (at anytime i will represent mx and (i+n-1)%n will represent mn. We will update our answer at each step. So, if we will divide a[i] by 2, it will become new mn. and next i will become mx and if we can't divide it by 2 (it is odd), we will stop because if we can't decrease max element, no point of decreasing other elements.
This exact question is on leetcode. Search Minimise deviation leetcode