FastPrep
Problem · Greedy

Break The Bricks 🐡

Learn this problem
● EasyMorgan StanleyINTERNOA

Problem statement

There are n bricks arranged in a row at positions numbered from 1 through n, inclusive. There is an array, newtons[n], that contains an integer indicating the number of newtons required to smash a brick. (A newton is a unit of force.)

There are two hammers, one big and one small. The big hammer can smash any brick with one blow. The small hammer reduces the newtons required by 1 for each blow to a brick. For example, a brick requires 3 newtons of force. It will take 1 blow with the big hammer, or 3 blows with the small hammer to smash it. There is a limit to how many times the big hammer can be used.

Determine 3 values:

  • the minimum number of blows to smash all the bricks
  • the 1-based indices of the bricks smashed by the big hammer, sorted ascending
  • the 1-based indices of the bricks smashed by the small hammer, sorted ascending
    • Return the values as a 2-dimensional integer array, [[total hits], [big hammer hits], [small hammer hits]]. If a hammer is not used, its index array should be [-1].

    Function

    stanleyBreakBricks(bigHits: int, newtons: int[]) → long[][]

    Complete the function breakTheBricks in the editor below.

    breakTheBricks has the following parameters:

  • int bigHits: the maximum blows with the big hammer
  • int newtons[n]: an array of distinct integers representing newtons required to smash each brick

    • Returns

    long[[1], [p][q]]: IN THE FORM [[total hits], [sorted indices for big hammer hits], [sorted indices for small hammer hits]]

    Examples

    Example 1

    bigHits = 0newtons = [2]return = [[2], [-1], [1]]

    The big hammer cannot be used. The small hammer takes 2 blows to smash the brick at index 1, so the result is [[2], [-1], [1]].

    Example 2

    bigHits = 4newtons = [3, 2, 5, 4, 6, 7, 9]return = [[13], [3, 5, 6, 7], [1, 2, 4]]

    Use the big hammer on the four strongest bricks, at indices 3, 5, 6, and 7. Those take 4 blows. The remaining bricks require 3 + 2 + 4 = 9 small-hammer blows, for 13 total.

    Example 3

    bigHits = 9newtons = [7, 9, 3, 2, 5, 8, 4, 6]return = [[8], [1, 2, 3, 4, 5, 6, 7, 8], [-1]]

    There are enough big-hammer blows for every brick. Each of the eight bricks takes one blow, and the small hammer is unused.

    Example 4

    bigHits = 0newtons = [10000000, 100000000, 1000000000]return = [[1110000000], [-1], [1, 2, 3]]

    With bigHits = 0, every brick uses the small hammer. The total is 10000000 + 100000000 + 1000000000 = 1110000000.

    Constraints

  • 1 ≤ n ≤ 2x105
  • 0 ≤ bigHits ≤ 2x105
  • 1 ≤ newtons[n] ≤ 109

    • More Morgan Stanley problems

    drafts saved locally
    public long[][] stanleyBreakBricks(int bigHits, int[] newtons) {
  // write your code here
}
    bigHits0
    newtons[2]
    expected[[2], [-1], [1]]
    checking account