Practice/Meta/Leetcode 1891. Cutting Ribbons

Leetcode 1891. Cutting Ribbons

CodingMust

Problem

You are given an array of positive integers representing the lengths of ribbons and a positive integer k representing the number of ribbon pieces you need. Your task is to determine the maximum possible length such that you can cut the ribbons into at least k pieces of that uniform length.

Each ribbon can be cut into multiple pieces of the target length (any leftover shorter than the target length is discarded). You need to find the largest integer length where the total number of pieces across all ribbons is at least k. If it's impossible to obtain k pieces, return 0.

Requirements

1. Return the maximum integer length that allows you to cut at least k pieces from all ribbons combined
2. Each ribbon can only be cut into pieces of the same target length
3. Partial pieces (remainders) cannot be used and are discarded
4. If obtaining k pieces is impossible, return 0
5. The solution should efficiently handle large inputs

Constraints

• 1 ≤ ribbons.length ≤ 105
• 1 ≤ ribbons[i] ≤ 105
• 1 ≤ k ≤ 109
• All lengths are positive integers

Examples

Example 1:

Input: ribbons = [9, 7, 5], k = 3 Output: 5 Explanation: Cut all ribbons into pieces of length 5. The first ribbon (length 9) gives 1 piece, the second ribbon (length 7) gives 1 piece, and the third ribbon (length 5) gives 1 piece, for a total of 3 pieces.

Example 2:

Input: ribbons = [7, 5, 9], k = 4 Output: 4 Explanation: With length 4, we get: 7÷4=1 piece, 5÷4=1 piece, 9÷4=2 pieces, totaling 4 pieces. If we try length 5, we only get 3 pieces total.

Example 3:

Input: ribbons = [5, 7, 9], k = 22 Output: 0 Explanation: Even if we cut each ribbon into pieces of length 1, we only get 5+7+9=21 pieces total, which is less than the required 22 pieces.

Example 4:

Input: ribbons = [1, 2, 3, 4, 9], k = 5 Output: 3 Explanation: With length 3, we get: 1÷3=0, 2÷3=0, 3÷3=1, 4÷3=1, 9÷3=3, totaling 5 pieces.