FastPrep
Problem · Heap

Last Stone Weight

Learn this problem
● EasyFactSetOA

Problem statement

Each day a quarry-worker is given a pile of stones and told to reduce the larger stones into smaller ones. The worker must smash the stones together to reduce them, and is told to always pick up the largest two stones and smash them together. If the stones are of equal weight, they both disintegrate entirely. If one is larger, the smaller one is disintegrated and the larger one is reduced by the weight of the smaller one. Eventually, there is either one stone left that cannot be broken, or all of the stones have been smashed. Determine the weight of the last stone, or return 0 if there is none.

Function

lastStoneWeight(weights: int[]) → int

Complete the function lastStoneWeight in the editor below. The function must return an integer that denotes the weight of the last stone, or 0 if all stones shattered into dust.

lastStoneWeight has the following parameter(s):

  1. int weights[n]: an array of integers indicating the weights of each stone

Examples

Example 1

weights = [1,2,3,6,7,7]return = 0

The worker always starts with the two largest stones. In this case, the two largest stones have equal weights of 7 so they both disintegrate when smashed. Next the worker smashes weights 3 and 6. The smaller one is destroyed and the larger weighs 6 - 3 = 3 units. Then, weights 3 and 2 are smashed together, which leaves a stone of weight 1. This is smashed with the last remaining stone of weight 1. There are no stones left, so the remaining stone weight is 0.

Constraints

  • 1 ≤ n ≤ 10^5
  • 1 ≤ weights[i] ≤ 10^9

    • More FactSet problems

    drafts saved locally
    public int lastStoneWeight(int[] weights) {
  // write your code here
}
    weights[1,2,3,6,7,7]
    expected0
    checking account