How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Meta.

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at Meta during technical interviews.

Optimize ribbon piece length by binary search

Quick Overview

This question evaluates understanding of binary-search-on-answer techniques and monotonic predicates, complexity analysis, and implementation-level handling of integer overflow and extreme edge cases in numeric partitioning, situated in the coding and algorithms domain and emphasizing practical implementation considerations rather than purely theoretical proofs. It is commonly asked because it reveals whether an interviewee can reason about monotonicity and design an O(n log max(lengths)) solution that remains robust under very large k, large element values, and potential integer overflow.

Optimize ribbon piece length by binary search

Company: Meta

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

Given an array lengths of positive integers and an integer k, you may cut each element into pieces of integer length L > 0. Find the maximum L such that you can obtain at least k pieces in total. If it is impossible to obtain k pieces, return 0. Constraints: 1 <= lengths.length <= 200000, 1 <= lengths[i] <= 1e9, 1 <= k <= 1e12. Design an O(n log max(lengths)) algorithm using a monotonic predicate and binary search over L. Be explicit about integer overflow handling and edge cases (e.g., very large k, many short lengths).

Quick Answer: This question evaluates understanding of binary-search-on-answer techniques and monotonic predicates, complexity analysis, and implementation-level handling of integer overflow and extreme edge cases in numeric partitioning, situated in the coding and algorithms domain and emphasizing practical implementation considerations rather than purely theoretical proofs. It is commonly asked because it reveals whether an interviewee can reason about monotonicity and design an O(n log max(lengths)) solution that remains robust under very large k, large element values, and potential integer overflow.

You are given an array `lengths` of positive integers and an integer `k`. You may cut each element into pieces of integer length `L > 0` (every piece from a single element has the same length `L`, and an element of size `x` yields `floor(x / L)` pieces). Find the maximum `L` such that you can obtain **at least** `k` pieces in total across all elements. If it is impossible to obtain `k` pieces, return `0`. The number of pieces obtainable for a fixed `L` is a monotonically non-increasing function of `L`: larger `L` never yields more pieces. This lets you binary search over `L` in `[1, max(lengths)]` using the predicate `canMake(L) = sum(x // L for x in lengths) >= k`. The largest `L` for which the predicate holds is the answer; if it never holds (even at `L = 1`, i.e. `sum(lengths) < k`), return `0`. Watch for overflow: `k` can be up to 1e12 and the total piece count can exceed 32-bit range, so accumulate in 64-bit (`long` in Java/C++). You can also early-exit the counting loop once the running count reaches `k`. Example: `lengths = [5, 9, 7]`, `k = 3`. At `L = 5`: `1 + 1 + 1 = 3 >= 3`, OK. At `L = 6`: `0 + 1 + 1 = 2 < 3`, fails. So the answer is `5`.

Constraints

1 <= lengths.length <= 200000
1 <= lengths[i] <= 1e9
1 <= k <= 1e12
All values in lengths are positive integers
Piece length L must be a positive integer (L > 0)

Examples

Input: ([5, 9, 7], 3)

Expected Output: 5

Explanation: At L=5: 1+1+1=3 pieces >= 3. At L=6: 0+1+1=2 < 3. So the maximum L is 5.

Input: ([9, 7, 5], 4)

Expected Output: 4

Explanation: At L=4: 2+1+1=4 pieces >= 4. At L=5: 1+1+1=3 < 4. Maximum L is 4.

Input: ([1, 2, 3], 10)

Expected Output: 0

Explanation: Even at L=1 we get only 1+2+3=6 pieces < 10, so it is impossible; return 0.

Input: ([1000000000], 1000000000)

Expected Output: 1

Explanation: A single ribbon of length 1e9 cut at L=1 yields exactly 1e9 pieces. Any L>1 yields fewer, so the answer is 1 (tests overflow-safe counting).

Input: ([10], 1)

Expected Output: 10

Explanation: We only need 1 piece, so the largest L that still yields a piece is the full length 10.

Input: ([4, 4, 4, 4], 4)

Expected Output: 4

Explanation: At L=4 each ribbon gives exactly 1 piece, totaling 4 >= 4. At L=5 none yield a piece. Maximum L is 4 (exact-divisor tie).

Input: ([2, 3], 7)

Expected Output: 0

Explanation: Max pieces at L=1 is 2+3=5 < 7, impossible; return 0.

Input: ([8, 12, 6], 6)

Expected Output: 4

Explanation: At L=4: 2+3+1=6 >= 6. At L=5: 1+2+1=4 < 6. Maximum L is 4.

Hints

The number of pieces you can make is non-increasing as L grows. This monotonicity is exactly what binary search needs.
Search L over the range [1, max(lengths)]. For a candidate L, count pieces as sum(x // L). The answer is the largest L where that count is >= k.
If sum(lengths) < k, even L = 1 can't reach k pieces, so return 0 immediately. Accumulate the piece count in a 64-bit integer since k can be up to 1e12, and early-break once the running count reaches k.

Last updated: Jun 26, 2026

Loading coding console...

Quick Overview

Optimize ribbon piece length by binary search

Company: Meta

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

Constraints

1 <= lengths.length <= 200000
1 <= lengths[i] <= 1e9
1 <= k <= 1e12
All values in lengths are positive integers
Piece length L must be a positive integer (L > 0)

Examples

Input: ([5, 9, 7], 3)

Expected Output: 5

Explanation: At L=5: 1+1+1=3 pieces >= 3. At L=6: 0+1+1=2 < 3. So the maximum L is 5.

Input: ([9, 7, 5], 4)

Expected Output: 4

Explanation: At L=4: 2+1+1=4 pieces >= 4. At L=5: 1+1+1=3 < 4. Maximum L is 4.

Input: ([1, 2, 3], 10)

Expected Output: 0

Explanation: Even at L=1 we get only 1+2+3=6 pieces < 10, so it is impossible; return 0.

Input: ([1000000000], 1000000000)

Expected Output: 1

Explanation: A single ribbon of length 1e9 cut at L=1 yields exactly 1e9 pieces. Any L>1 yields fewer, so the answer is 1 (tests overflow-safe counting).

Input: ([10], 1)

Expected Output: 10

Explanation: We only need 1 piece, so the largest L that still yields a piece is the full length 10.

Input: ([4, 4, 4, 4], 4)

Expected Output: 4

Explanation: At L=4 each ribbon gives exactly 1 piece, totaling 4 >= 4. At L=5 none yield a piece. Maximum L is 4 (exact-divisor tie).

Input: ([2, 3], 7)

Expected Output: 0

Explanation: Max pieces at L=1 is 2+3=5 < 7, impossible; return 0.

Input: ([8, 12, 6], 6)

Expected Output: 4

Explanation: At L=4: 2+3+1=6 >= 6. At L=5: 1+2+1=4 < 6. Maximum L is 4.

Hints

The number of pieces you can make is non-increasing as L grows. This monotonicity is exactly what binary search needs.
Search L over the range [1, max(lengths)]. For a candidate L, count pieces as sum(x // L). The answer is the largest L where that count is >= k.
If sum(lengths) < k, even L = 1 can't reach k pieces, so return 0 immediately. Accumulate the piece count in a 64-bit integer since k can be up to 1e12, and early-break once the running count reaches k.

Last updated: Jun 26, 2026

Loading coding console...