[Solved]: Algorithm for fastest division below threshold

Problem Detail: 

Take a number i. You need to split it in two pieces as many times as necessary so that all splits are less than or equal to j. How does one obtain this with the minimum number of splits? Examples:

Splitting it in half is optimal here:

i = 4, j = 2 4 -> 2, 2 // (1 split) 

However, splitting in half is not optimal here:

i = 9, j = 3 9 -> 5, 4 // Split nine in half 5 -> 3, 2 // Then you have to split the 5 4 -> 2, 2 // and the 4 (3 splits) 

The optimal solution here would be:

i = 9, j = 3 9 -> 6, 3 6 -> 3, 3 // (2 splits) 

Is there some straightforward way to obtain the optimal split without brute-force iteration?

Asked By : dthree

Answered By : Yuval Filmus

The optimal strategy is the greedy one: repeatedly split chunks of size $j$. This strategy results in $\lceil \frac{i}{j} \rceil - 1$ splits. We can prove that this strategy is optimal by induction on $i$. The strategy is clearly optimal for $i \leq j$. Now suppose that we split $i > j$ as $i = i_1 + i_2$. In total, this choice will use up at least this many splits: $$ 1 + \lceil \tfrac{i_1}{j} \rceil - 1 + \lceil \tfrac{i_2}{j} \rceil - 1 = \lceil \tfrac{i_1}{j} \rceil + \lceil \tfrac{i_2}{j} \rceil - 1. $$ Let $\alpha = i/j$, $\alpha_1 = i_1/j$, $\alpha_2 = i_2/j$, so that $\alpha = \alpha_1 + \alpha_2$. To complete the proof, notice that $\lceil \alpha_1 \rceil + \lceil \alpha_2 \rceil \geq \lceil \alpha \rceil$, and so the quantity above is always at least $\lceil \tfrac{i}{j} \rceil - 1$, as claimed.

I have described one optimal strategy. Using the proof above, we can actually describe all optimal strategies. Splitting $i$ to $i_1+i_2$ is optimal iff $\lceil \frac{i_1}{j} \rceil + \lceil \frac{i_2}{j} \rceil = \lceil \frac{i}{j} \rceil$. When does that happen? Define $$ i = aj-b, \quad i_1 = a_1j-b_1, \quad i_2 = a_2j-b_2, $$ where $0 \leq b,b_1,b_2 < j$. A splitting is optimal iff $a_1 + a_2 = a$. Notice that $$ i_2 + i_2 = (a_1+a_2)j - b_1 - b_2. $$ This shows that the splitting is optimal iff $b_1 + b_2 = b$ (rather than $b + j$).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/41262