Optimize ribbon piece length by binary search
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.
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).