Find the minimum length of rope

user_12177212 0
Viewed 518

I have the following programming question:

Given as input an array of integer lengths with each element denoting the length of the rope required, find the minimum length of the original rope given that at each step, you can only half the length of a rope and the length of each rope must be an integer. Output -1 if no such rope exists.

Additional information on "halving" a rope of length x:

  • if x is divisible by 2, then the two resulting ropes would be of length x/2
  • otherwise, the two resulting ropes would be of length floor(x/2) and ceiling(x/2)

For example, if I require [3, 5, 2], then the minimum size rope I would require is 10 since '10' can be split into 2 '5's and one of the remaining '5' can be split into '3' and '2'. Then, I would end up with exactly what I require [3, 5, 2]. It is also allowed to end up with excessive rope that is not required.

I am provided with a function that can determine if a rope of a particular length can be split into the required lengths.

I was initially thinking of doing some sort of binary search in the search space [max length of rope required, ___], but I wasn't sure of what the upper bound should be. Also, I realised this wouldn't necessarily work since longer ropes does not necessarily guarantee that the rope can be split into the required lengths.

Right now, the only solution I have is a linear search, but this seems to be too slow and I'm not exactly sure the conditions that would result in there being no valid ropes.

Any guidance is greatly appreciated!

puzzle algorithm
1 Answers

Consider any required segment length m, and assume that we want to obtain this segment by halving a rope exactly k times. Then the shortest rope we would consider has length (2^k)*m - 2^k + 1. If we cut this rope in half k times, discarding the shorter half in every step, then we end up with a segment of length m. The longest rope we would consider has length (2^k)*m + 2^k - 1. If we cut this rope in half k times, discarding the longer half in every step, then we also end up with a segment of length m.

For our length m segment, we thus only have to consider ropes whose length is in the interval [(2^k)*m - 2^k + 1, (2^k)*m + 2^k - 1] for some positive integer k. Under the reasonable assumption that the final rope length can be represented by a 64bit unsigned integer, k is at most 64. Thus, using our interval notation from above, there are only 64 intervals that contain all possible rope lengths that can be used to obtain a length m segment.

Now here comes the fun part: Lets say there are n required segments of lenghts m_1, m_2, ..., m_n. For any segment m_i, we formally define the k-th candidate interval as:

I(m_i, k) = [(2^k)*m_i - 2^k + 1, (2^k)*m_i + 2^k - 1]

For any segment m_i, let X(m_i) denote the union of the 64 candidate intervals I(m_i, 1), I(m_i, 2), ..., I(m_i, 64). We know that the length x of the solution rope must be contained in each of the n sets X(m_1), X(m_2), ..., X(m_n). Thus, we have narrowed down the search space for the solution to the intersection of all the X(m_i).

You can efficiently iterate over all values in the search space by first generating the 64 * n intervals I(m_i, k), each represented by a pair of integers in your favorite programming language (careful with overflows!). Then you sort these pairs by their first component (i.e. by their left interval border) using a fast integer sorter, e.g. radix sort. Finally, iterating over the search space only requires a careful left-to-right scan over the sorted intervals, checking for the required intersection at all times (I'm purposefully omitting some technical details here).

Take for example the required segments [7,7,8,14] with shortest rope 57:

I(7, 1) = [13, 15]
I(7, 2) = [25, 31]
I(7, 3) = [49, 63]
I(7, 4) = [97, 127]
...

I(8, 1) = [15, 17]
I(8, 2) = [29, 35]
I(8, 3) = [57, 71]
I(8, 4) = [113, 143]
...

I(14, 1) = [27, 29]
I(14, 2) = [53, 59]
I(14, 3) = [105, 119]
...

Search Space: [29,29], [57,59], [113,119], ...

As you can see, the search space has become significantly smaller, such that the solution is actually the second smallest element of the search space!

Hope this helps ;)

user_142344440
Related