Cutting ribbons

XXX. Maximum Ribbon Length

Binary Search

Array

Problem Statement:

Given an array of ribbon lengths and an integer k, find the maximum length l where you can cut k ribbons of length l from the original ribbons.

• Each piece must have equal length
• Need exactly k total pieces
• Maximize the length of each piece

Implementation:

public int maxLength(int[] ribbons, int k) {
    // Binary search bounds
    int left = 1;                               // Start from 1, not 0
    int right = Arrays.stream(ribbons).max().getAsInt();

    // Binary search for maximum length
    while (left <= right) {
        int middle = left + (right - left) / 2; // Avoid overflow
        if (isPossible(middle, ribbons, k)) {
            left = middle + 1;                  // Try larger lengths
        } else {
            right = middle - 1;                 // Try smaller lengths
        }
    }
    return right;                              // Maximum valid length
}

private boolean isPossible(int x, int[] ribbons, int k) {
    int totalRibbons = 0;
    for (int ribbon : ribbons) {
        totalRibbons += ribbon / x;            // Count pieces
        if (totalRibbons >= k)                 // Early exit
            return true;
    }
    return false;
}

Complexity:

Time Complexity: O(n * log(M)) where M is max ribbon length
Space Complexity: O(1)

Key Differences from Other Version:

• **Binary Search Implementation**:
  • Uses left <= right condition
  • Standard midpoint calculation to avoid overflow
  • Returns right pointer as final answer
• **Search Range**:
  • Starts from 1 instead of 0
  • Moves pointers inclusively
  • Right pointer ends at answer

Example Walkthrough:

For ribbons [9,7,5] and k = 4:

• Binary search process:
  • Initial range: [1, 9]
  • Try mid=5: Can make 3 pieces (not enough)
  • Try mid=3: Can make 6 pieces (possible)
  • Try mid=4: Can make 4 pieces (possible)
  • Try mid=5: Can make 3 pieces (not enough)
  • Final answer: 4

Implementation Notes:

• **Optimization Features**:
  • Early exit in isPossible
  • Safe midpoint calculation
  • Avoids zero-length edge case
• **Binary Search Pattern**:
  • Moves left pointer past valid solutions
  • Right pointer ends at answer
  • Uses inclusive ranges throughout