Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1891.html

1891. Cutting Ribbons

Level

Medium

Description

You are given an integer array ribbons, where ribbons[i] represents the length of the i-th ribbon, and an integer k. You may cut any of the ribbons into any number of segments of positive integer lengths, or perform no cuts at all.

  • For example, if you have a ribbon of length 4, you can:
    • Keep the ribbon of length 4,
    • Cut it into one ribbon of length 3 and one ribbon of length 1,
    • Cut it into two ribbons of length 2,
    • Cut it into one ribbon of length 2 and two ribbons of length 1, or
    • Cut it into four ribbons of length 1.

Your goal is to obtain k ribbons of all the same positive integer length. You are allowed to throw away any excess ribbon as a result of cutting.

Return the maximum possible positive integer length that you can obtain k ribbons of, or 0 if you cannot obtain k ribbons of the same length.

Example 1:

Input: ribbons = [9,7,5], k = 3

Output: 5

Explanation:

  • Cut the first ribbon to two ribbons, one of length 5 and one of length 4.
  • Cut the second ribbon to two ribbons, one of length 5 and one of length 2.
  • Keep the third ribbon as it is.

Now you have 3 ribbons of length 5.

Example 2:

Input: ribbons = [7,5,9], k = 4

Output: 4

Explanation:

  • Cut the first ribbon to two ribbons, one of length 4 and one of length 3.
  • Cut the second ribbon to two ribbons, one of length 4 and one of length 1.
  • Cut the third ribbon to three ribbons, two of length 4 and one of length 1.

Now you have 4 ribbons of length 4.

Example 3:

Input: ribbons = [5,7,9], k = 22

Output: 0

Explanation: You cannot obtain k ribbons of the same positive integer length.

Constraints:

  • 1 <= ribbons.length <= 10^5
  • 1 <= ribbons[i] <= 10^5
  • 1 <= k <= 10^9

Solution

Use binary search. Initialize low as 0 and high as the maximum in ribbons. Each time let mid = (high - low + 1) / 2 + low and calculate the number of ribbons that can be obtained with length mid. If the number of ribbons is greater than or equal to k, then the length is at least mid, so let low = mid. Otherwise, the length is at most mid - 1, so let high = mid - 1. Finally, return low as the maximum possible length.

  • class Solution {
    public int maxLength(int[] ribbons, int k) {
        int maxRibbon = 0;
        for (int ribbon : ribbons)
            maxRibbon = Math.max(maxRibbon, ribbon);
        int low = 0, high = maxRibbon;
        while (low < high) {
            int mid = (high - low + 1) / 2 + low;
            int count = 0;
            for (int ribbon : ribbons)
                count += ribbon / mid;
            if (count >= k)
                low = mid;
            else
                high = mid - 1;
        }
        return low;
    }
}

############

class Solution {
    public int maxLength(int[] ribbons, int k) {
        int left = 0, right = 100000;
        while (left < right) {
            int mid = (left + right + 1) >>> 1;
            int cnt = 0;
            for (int x : ribbons) {
                cnt += x / mid;
            }
            if (cnt >= k) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
}

  • class Solution {
public:
    int maxLength(vector<int>& ribbons, int k) {
        int low = 0, high = 100000;
        while (low < high) {
            int mid = (low + high + 1) / 2;
            int cnt = 0;
            for (auto ribbon : ribbons) {
                cnt += ribbon / mid;
            }
            if (cnt < k) {
                high = mid - 1;
            } else {
                low = mid;
            }
        }
        return low;
    }
};

  • class Solution:
    def maxLength(self, ribbons: List[int], k: int) -> int:
        low, high = 0, 100000
        while low < high:
            mid = (low + high + 1) >> 1
            cnt = 0
            for ribbon in ribbons:
                cnt += ribbon // mid
            if cnt < k:
                high = mid - 1
            else:
                low = mid
        return low



  • func maxLength(ribbons []int, k int) int {
	left, right := 0, 100000
	for left < right {
		mid := (left + right + 1) >> 1
		cnt := 0
		for _, x := range ribbons {
			cnt += x / mid
		}
		if cnt >= k {
			left = mid
		} else {
			right = mid - 1
		}
	}
	return left
}

  • function maxLength(ribbons: number[], k: number): number {
    let left = 0;
    let right = 1e5;
    while (left < right) {
        const mid = (left + right + 1) >> 1;
        let cnt = 0;
        for (const x of ribbons) {
            cnt += Math.floor(x / mid);
        }
        if (cnt >= k) {
            left = mid;
        } else {
            right = mid - 1;
        }
    }
    return left;
}


  • /**
 * @param {number[]} ribbons
 * @param {number} k
 * @return {number}
 */
var maxLength = function (ribbons, k) {
    let left = 0;
    let right = 1e5;
    while (left < right) {
        const mid = (left + right + 1) >> 1;
        let cnt = 0;
        for (const x of ribbons) {
            cnt += Math.floor(x / mid);
        }
        if (cnt >= k) {
            left = mid;
        } else {
            right = mid - 1;
        }
    }
    return left;
};


  • impl Solution {
    fn max_length(ribbons: Vec<i32>, k: i32) -> i32 {
        let mut left = 0i32;
        let mut right = *ribbons.iter().max().unwrap();
        while left < right {
            let mid = (left + right + 1) / 2;
            let mut cnt = 0i32;
            for &entry in ribbons.iter() {
                cnt += entry / mid;
                if cnt >= k {
                    break;
                }
            }
            if cnt >= k {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
}

All Problems

All Solutions