We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Cutting Ribbons

Number: 2045

Difficulty: Medium

Paid? Yes

Companies: Meta, Google

Problem Description

Given an array of integers representing ribbon lengths and an integer k, the objective is to determine the maximum integer length x such that it is possible to cut the given ribbons into at least k pieces of length x. You may cut any ribbon into pieces of positive integer lengths (or leave it unchanged) and can discard any excess.

Key Insights

  • Use binary search to determine the maximum possible ribbon length x.
  • For a candidate length, count the total pieces obtainable across all ribbons by computing (ribbon_length // candidate_length).
  • The search space can be set from 1 to the maximum ribbon length since no piece can be longer than the longest ribbon.
  • If the total pieces are at least k, the candidate length is feasible, so try a larger length; otherwise, try a smaller length.

Space and Time Complexity

Time Complexity: O(n * log(max(ribbon_length))) where n is the number of ribbons. Space Complexity: O(1) (excluding the input storage).

Solution

The problem is solved using binary search on the possible ribbon lengths. The algorithm initializes the search boundaries as 1 and the maximum ribbon length. At each iteration, it computes mid as the current candidate length and checks if at least k pieces can be made by iterating through the ribbons and adding up (ribbon // mid) for each ribbon. If the candidate length is valid, the algorithm continues searching to the right; otherwise, it searches to the left. The final maximum valid length is returned if one exists, otherwise 0.

Code Solutions

# Python solution for Cutting Ribbons

def maxRibbonLength(ribbons, k):
    # Helper function to determine if it's possible to obtain at least k pieces of a given length
    def is_possible(length):
        total_pieces = 0
        # Iterate each ribbon to count pieces of the given length
        for ribbon in ribbons:
            total_pieces += ribbon // length
        return total_pieces >= k

    # Initializing binary search boundaries: low is 1 and high is the maximum ribbon length
    low, high = 1, max(ribbons)
    result = 0  # variable to store the maximum valid ribbon length found
    
    while low <= high:
        mid = (low + high) // 2
        # Check if it's possible to cut ribbons into pieces of length mid
        if is_possible(mid):
            result = mid  # mid is possible, update result
            low = mid + 1  # try to find a larger possible length
        else:
            high = mid - 1  # mid is not possible, search for a smaller length
    return result

# Example usage:
# print(maxRibbonLength([9,7,5], 3))  # Output: 5
← Back to All Questions