You are given n identical segments, each of length 1, and an integer m. The total length of all segments must be divided equally among m recipients, so each recipient receives pieces with a total length of exactly n / m. A single share may consist of several pieces, including pieces from different segments.
Each cut splits one piece into two shorter pieces at any point you choose. The segments start uncut.
Return the minimum number of cuts needed so that the resulting pieces can be partitioned into m groups of equal total length.
Input: n = 2, m = 6
Output: 4
Explanation: Each share must have length 2/6 = 1/3. Cut each segment into three
pieces of length 1/3 (2 cuts per segment). The 6 pieces form the 6 equal shares.
Input: n = 6, m = 4
Output: 2
Explanation: Each share must have length 6/4 = 3/2. Cut two segments in half
(1 cut each). Each recipient gets one whole segment plus one half segment.
Input: n = 5, m = 5
Output: 0
Explanation: Each recipient gets one whole segment; no cuts are needed.
n ≤1000m ≤1000