### guesshere's blog

By guesshere, history, 2 months ago,

You are given an array of positive numbers. You can can convert any element (i) to any value in range [i/2, i-1] or [i+1, 2*i] in one step. Mind minimum steps needed to make the all elements equal.

1 <= n <= 1e5

Each element in range [1,1e5]

• 0

 » 2 months ago, # | ← Rev. 3 →   +13 I think I found a solution.First off, let's try to fix the element we will convert all elements into and minimize the step count across all elements. Can we calculate the minimum steps in $O(\log n)$? Turns out we can. Let $x$ be the final element. First, we need a frequency array. Now we will use this to find all elements in a certain interval. It is clear we can find the number of elements in the interval $[x,2x]$ in $O(1)$ by turning the frequency array into a prefix sum array. We can do the same for $[x,\frac {x}{2}]$. For both of these we add $1$ to the total step count. For the interval $[2x,4x]$ though the step count will be 2, same goes for $[\frac {x}{2},\frac {x}{4}]$. The amount of such segments will clearly be $O(\log n)$. Since there's only $10^5$ possible final elements, the total time complexity will be $O(n \log n)$I'm sorry if I got this wrong
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 Let target element be 10 so according to you any element in range [10,20] will take 1 move(s) [20,40] will take 2 move(s) [40,80] will take 3 move(s)So let's take the element 50 which is to be converted to 10 : Then 50 -> 25 -> 12 -> 10 (3 moves)
•  » » » 2 months ago, # ^ |   0 Yeah, this approach seems right. You can also think about it as having only log(n) checkpoints that matter. So instead of 50->25->12-10, you can do 50->40->20->10 since the checkpoints are powers of 2 times your target (10), and there are log(n) ranges that matter.
•  » » » » 2 months ago, # ^ |   0 Thank you!