CODEWITHSUNDEEP
algorithmnumbers
xcoder
xcoder

Reputation: 1436

Number of steps taken to split a number

I cannot get my head around this:

Say I got a number 9. I want to know the minimum steps needed to split it so that no number is greater than 3.

I always thought that the most efficient way is to halve it every loop. So, 9 -> 4,5 -> 2,2,5 -> 2,2,2,3 so 3 steps in total. However, I just realised a smarter way: 9 -> 3,6 -> 3,3,3 which is 2 steps only...

After some research, the number of steps is in fact (n-1)/target, where target=3 in my example.

Can someone please explain this behaviour to me?

Upvotes: 0

Views: 113

Answers (3)

Paul Boddington
Paul Boddington

Reputation: 37645

I really like @user2357112's explanation of why cutting in half is not the right first step, but I also like algebra, and you can prove that ceil(n / target) - 1 is optimal using induction.

Let's prove first that you can always do it in ceil(n / target) - 1 steps.

If n <= target, obviously no step are required, so the formula works. Suppose n > target. Split n into target and n - target (1 step). By induction, n - target can be split in ceil((n - target)/target) - 1 steps. Therefore the total number of steps is 

  1 + ceil((n - target) / target) - 1

= 1 + ceil(n / target) - target/target - 1

= ceil(n / target) - 1.

Now let's prove that you can't do it in fewer than ceil(n / target) - 1 steps. This is obvious if n <= target. Suppose n > target and the first step is n -> a + b. By induction, a requires at least ceil(a / target) - 1 steps and b requires at least ceil(b / target) - 1 steps. The minimum number of steps required is therefore at least

   1 + ceil(a / target) - 1 + ceil(b / target) - 1

>= ceil((a + b) / target) - 1                using ceil(x) + ceil(y) >= ceil(x + y)

 = ceil(n / target) - 1                      using a + b = n

Upvotes: 1

user2357112
user2357112

Reputation: 280301

If we want to cut a stick of length L into pieces of size no greater than S, we need ceiling(L/S) pieces. Each time we make a new cut, we increase the number of pieces by 1. It doesn't matter what order we make the cuts in, only where. For example, if we want to break a stick of length 10 into pieces of size 2 or less:

 -------------------
0 1 2 3 4 5 6 7 8 9 10

we should cut it in the following places:

 ---|---|---|---|---
0 1 2 3 4 5 6 7 8 9 10

and any order of cuts is fine, as long as these are the cuts that are made. On the other hand, if we start by breaking it in half:

 ---------|---------
0 1 2 3 4 5 6 7 8 9 10

we have made a cut that isn't part of the optimal solution, and we have wasted our time.

Upvotes: 3

vrume21
vrume21

Reputation: 551

Every n can be thought of as a priority queue of \lfloor n/target \rfloor target elements placed first on the queue and one element whose value is n%target. Every time you remove an element from the queue, you place it back on the queue. Remove all but the last element: you have clearly removed \lfloor (n-1)/target \rfloor elements. If the last element is less than or equal to the target, we are done. If it is greater than the target, we have a contradiction. So, after \lfloor (n-1)/target \rfloor steps we have a queue consisting only of elements less than or equal to target.

Upvotes: 0

Related Questions