Description
Solutions
Smash The Bricks(NG)
🔥 FULLTIME

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 Description

    Complete the function smashTheBricks in the editor below.

    smashTheBricks has the following parameters:

    1. int bigHits: the maximum blows with the big hammer
    2. int newtons[n]: the newtons required to smash each brick

    Returns

    long [][], [p][q]: in the form [[ total hits], [sorted indices for big hammer hits], [sorted indices for small hammer hits]]

    Example 1: 

    Input:  bigHits = 0, newtons = [2]
    Output: [[2], [-1], [1]] 
    Explanation:
    
The big hammer cannot be used. The small hammer takes 2 blows to smash the single brick at index 1. The return array is [[2], [-1], [1]].

    Example 2: 

    Input:  bigHits = 4, newtons = [3, 2, 5, 4, 6, 7, 9]
    Output: [[13], [3, 5, 6, 7], [1, 2, 4]] 
    Explanation:
    
In this case, it is best to use the big hammer on bricks at sorted indices [3, 5, 7], using 4 hits to smash them all. The small hammer is used on sorted indices [1, 2, 4], which have newtons of 3, 2, and 4. It takes a total of 3 + 2 + 4 = 9 hits with the small hammer. The total blows required = 4 + 9 = 13. The return array is [[13], [3, 5, 6, 7], [1, 2, 4]].

    Example 3: 

    Input:  bigHits = 9, newtons = [7, 9, 3, 2, 5, 8, 4, 6]
    Output: [[8], [1, 2, 3, 4, 5, 6, 7, 8], [-1]] 
    Explanation:
    
There are enough bigHits available to smash all of the bricks with the large hammer. The returned arr is [[8], [1, 2, 3, 4, 5, 6, 7, 8], [-1]]:)

    Example 4: 

    Input:  bigHits = 0, newtons = [10000000, 100000000, 1000000000]
    Output: [[1110000000], [-1], [1, 2, 3]] 
    Explanation:
    
Since bigHits =0, the big hammer cannot be used. The toal hits required is the sum of the newtons arr, one hit with a small hammer for each newton. The returned arr is [[1110000000], [-1], [1, 2, 3]] :P
    Constraints:
    • 1 ≤ n ≤ 2 x 105
    • 0 ≤ bigHits ≤ 2 x 105
    • 1 ≤ newtons[i] ≤ 109
    • Elements in newtons[] are distinct.
    Thumbnail 0
    Testcase
    Result
    Case 1

    input:

    output: