Practice: The Longest Equal Pieces Three Ropes Can Make

Cut ropes of 11, 8 and 6 metres into at least 5 pieces of the same whole-metre length: find the longest length that works.

Searching over possible answers works for a largest value as well as a smallest one, once the predicate and its direction are named. A stagehand has ropes of 11, 8 and 6 metres and needs at least 5 pieces of exactly the same length, in whole metres, with any leftover thrown away. Pieces cannot be joined. Find the longest length that gives at least 5 pieces, by binary search, and say which way mid must round.

Show the answer and a solution

4 metres: 2 pieces from the 11, 2 from the 8 and 1 from the 6, which is 5. At 5 metres there are only 2 + 1 + 1 = 4. The predicate is "length L gives at least 5 pieces", and the pieces from a rope of v are v // L, rounded down. Longer pieces never give more of them, so the predicate is true for short lengths and false from some length on: the answer is the last true. On a true, low moves to mid; on a false, high moves to mid − 1; and because low moves to mid, mid must round up.

Searching the lengths 1 to 11 for the last that gives 5 pieces

Inputropes 11 8 6, at least 5 pieces

Start
1. 1low
2. 2
3. 3
4. 4
5. 5
6. 6
7. 7
8. 8
9. 9
10. 10
11. 11high
Any length from 1 to 11 metres, the longest rope, could be the answer
Length 6: 3 pieces
1. 1low
2. 2
3. 3
4. 4
5. 5
6. 6mid
7. 7
8. 8
9. 9
10. 10
11. 11high
6 metres gives 3 pieces, too few: high moves to 5
Length 3: 7 pieces
1. 1low
2. 2
3. 3mid
4. 4
5. 5high
6. 6
7. 7
8. 8
9. 9
10. 10
11. 11
3 metres gives 7 pieces, enough: low moves to 3
Length 4: 5 pieces
1. 1
2. 2
3. 3low
4. 4mid
5. 5high
6. 6
7. 7
8. 8
9. 9
10. 10
11. 11
4 metres gives 5 pieces, enough: low moves to 4
Length 5: 4 pieces
1. 1
2. 2
3. 3
4. 4low
5. 5midhigh
6. 6
7. 7
8. 8
9. 9
10. 10
11. 11
5 metres gives 4 pieces, too few: high moves to 4
Done
1. 1
2. 2
3. 3
4. 4lowhigh
5. 5
6. 6
7. 7
8. 8
9. 9
10. 10
11. 11
low meets high at 4 metres

ResultThe longest length that gives at least 5 pieces is 4 metres.

The listing prints each length it tests and the pieces that length gives.

ropes.pypy

ropes = [11, 8, 6]
needed = 5


def pieces(length: int) -> int:
    return sum(rope // length for rope in ropes)


low, high = 1, max(ropes)
while low < high:
    mid = low + (high - low + 1) // 2
    count = pieces(mid)
    print(f"length {mid}: {count} pieces")
    if count >= needed:
        low = mid
    else:
        high = mid - 1
print(f"longest length: {low} metres")

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

length 6: 3 pieces
length 3: 7 pieces
length 4: 5 pieces
length 5: 4 pieces
longest length: 4 metres

The search tests 4 lengths where trying each from 11 downwards would test 8, and each test reads all n ropes, so it is O(n log m) for a longest rope of m. Rounding mid down here would test 5 and then 4 again for ever once low was 4 and high 5, the loop the gotcha describes.

Binary Search

← → move through sections and cards