FastPrep
Problem · Array

Cut the Sticks

Learn this problem
● EasyMicrosoft logoMicrosoftINTERNOA
See Microsoft hiring insights

Problem statement

Given an array of positive integer rod lengths lengths, repeatedly perform cutting rounds while at least one rod remains.

At the start of each round, record the number of remaining rods. Then subtract the length of the shortest remaining rod from every remaining rod. Remove every rod whose length becomes 0.

Return the recorded rod counts in round order.

Function

cutSticks(lengths: int[]) → int[]

Examples

Example 1

lengths = [1,1,3,4]return = [4,2,1]

The first round starts with 4 rods and removes the two rods of length 1. The remaining lengths are [2, 3]. The next two rounds start with 2 rods and then 1 rod.

Example 2

lengths = [5,4,4,2,2,8]return = [6,4,2,1]

The distinct positive lengths are 2, 4, 5, and 8. Respectively, 6, 4, 2, and 1 rods remain when those levels are removed.

Constraints

  • 1 <= lengths.length <= 200000
  • 1 <= lengths[i] <= 1000000000

More Microsoft problems

drafts saved locally
public int[] cutSticks(int[] lengths) {
    // write your code here
}
lengths[1,1,3,4]
expected[4,2,1]
checking account