Cutting Ribbons - Practice Coding Problems

Cutting Ribbons - Problem

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
Cut it into four ribbons of length 1

Your task is to determine the maximum length of ribbon, x, that allows you to cut at least k ribbons, each of length x. You can discard any leftover ribbon from the cuts.

If it is impossible to cut k ribbons of the same length, return 0.

Input & Output

Example 1 — Basic Case

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

› Output: 5

💡 Note: We can cut the ribbons as follows: 9÷5=1 piece, 7÷5=1 piece, 5÷5=1 piece. Total = 3 pieces of length 5.

Example 2 — Multiple Cuts Per Ribbon

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

› Output: 4

💡 Note: Cut ribbons: 7÷4=1 piece, 5÷4=1 piece, 9÷4=2 pieces. Total = 4 pieces of length 4.

Example 3 — Impossible Case

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

› Output: 0

💡 Note: Even cutting all ribbons into pieces of length 1 gives us only 5+7+9=21 pieces, which is less than 22.

Constraints

1 ≤ ribbons.length ≤ 10⁵
1 ≤ ribbons[i] ≤ 10⁵
1 ≤ k ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Array of ribbon lengths and target count k

Process

Find maximum length x where total cuts ≥ k

Output

Maximum valid ribbon length or 0 if impossible

Key Takeaway

🎯 Key Insight: Use binary search on the answer space since feasibility is monotonic

Asked in

G Google 25 a Amazon 20 f Meta 15

The key insight is to use binary search on the answer space. If we can cut k ribbons of length x, we can also cut k ribbons of any smaller length. Best approach is binary search with Time: O(n × log(max_length)), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Binary Search on Answer	O(n × log(max_length))	O(1)	Binary search on the possible ribbon length range to find maximum valid length
Brute Force Linear Search	O(n × max_length)	O(1)	Try every possible ribbon length from maximum down to 1

Binary Search on Answer — Algorithm Steps

Set search range: left=1, right=max(ribbons)
Binary search on possible lengths
For each mid length, count total possible cuts
If cuts ≥ k, search right half; else search left half

Visualization

Tap to expand

Step-by-Step Walkthrough

Set Range

Initialize left=1, right=max(ribbons)

Test Middle

Check if mid length allows k cuts

Narrow Range

Adjust search bounds based on feasibility

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int canCutKRibbons(int* ribbons, int ribbonsSize, int k, int length) {
    int totalCuts = 0;
    for (int i = 0; i < ribbonsSize; i++) {
        totalCuts += ribbons[i] / length;
    }
    return totalCuts >= k;
}

int solution(int* ribbons, int ribbonsSize, int k) {
    if (ribbonsSize == 0) {
        return 0;
    }
    
    int maxLength = ribbons[0];
    for (int i = 1; i < ribbonsSize; i++) {
        if (ribbons[i] > maxLength) {
            maxLength = ribbons[i];
        }
    }
    
    int left = 1, right = maxLength;
    int result = 0;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (canCutKRibbons(ribbons, ribbonsSize, k, mid)) {
            result = mid;
            left = mid + 1;  // Try for longer length
        } else {
            right = mid - 1;  // Try shorter length
        }
    }
    
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple array parsing
    int ribbons[1000];
    int ribbonsSize = 0;
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        if (strlen(token) > 0) {
            ribbons[ribbonsSize++] = atoi(token);
        }
        token = strtok(NULL, "[],\n");
    }
    
    int k;
    scanf("%d", &k);
    
    int result = solution(ribbons, ribbonsSize, k);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × log(max_length))

Binary search takes log(max_length) iterations, each iteration counts cuts in O(n) time

⚡ Linearithmic

Space Complexity

O(1)

Only using variables for binary search bounds and counting, no extra data structures

✓ Linear Space

23.4K Views

Medium Frequency

~25 min Avg. Time

845 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Binary Search on Answer — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler