This Problem appeared on my Oracle OA and I don’t have any working solution or proper proof of what is the correct approach for this
You’re given an array and we need to find the minimum number of operations to make all elements equal
In one operation you can change a[i] and set it to new value
The allowed operations are:
1. arr[i] → any value in range [arr[i] + 1, arr[i] * 2]
2. arr[i] → any value in range [ceil(arr[i]/2), arr[i]-1]
You can perform either of these two types of operations any number of times (on any elements, in any order). You have to output the minimum number of operations to make all elements equal.
1 ≤ n ≤ 1e5
1 ≤ arr[i] ≤ 1e9
I tried making everything equal to the median, but it fails on this case:
9 10 12 30 1000
Converting to median takes 11 operations
but the ans is 10 (Converting every element to 16)
It is sort of related to logarithmic median (not a standard term) . Make a new array = original + all ceils and 2*x from all nums in original . From each element try to reach every other element with ops , add range operation in Operations_store_array . minimum valued accumulated at an index of operations_store_array is ans .
*i mean final length will be O(31*n)
I guess following should work,
For every element store intervals for eg for el, store [el+1,2*el],[2*el+1,4*el],[4*el+1,8*el].. until upper bound cross 1e9 and similarly store those for ceil operation until lower bound is greater than 1.
There will be atmost 30 interval for each element.
Now cost only change at these intervals endpoints so you just have to calculate cost to convert array to an endpoint and do it for every endpoint and take minimum of it.
There may be atmost 60*n endpoints
To do it optimally you can keep two map and update +1 to every left endponint in map similar to difference array and take prefix and suffix sums on that map.