Last Stone Weight

Easy

0/40

Average time to solve is 27m

Contributed by

31 upvotes

Asked in companies

Problem statement

We have a collection of 'N' stones, each stone has a positive integer weight.

On each turn, we choose the two heaviest stones and smash them together. Suppose the stones have weights 'x' and 'y' with 'x' <= 'y'. The result of this smash will be:

1. If 'x' == 'y', both stones are totally destroyed;

2. If 'x' != 'y', the stone of weight 'x' is totally destroyed, and the stone of weight 'y' has a new weight equal to 'y - x'.

In the end, there is at most 1 stone left. Return the weight of this stone or 0 if there are no stones left.

Detailed explanation ( Input/output format, Notes, Images )

Input format:

The first line of input contains the integer 'N', representing the total number of stones.

The second line of input contains 'N' single space-separated integers, representing the weights of the stones.

Output Format:

The only output line prints the weight of the last stone, if it exists, 0 otherwise.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given functions.

Constraints :

1 <= N <= 10^5
1 <= W <= 10^6

Time Limit: 1 sec

Sample Input 1:

1
10

Sample Output 1:

Explanation For Sample Input 1:

There is Only one stone so the weight of the last stone is 10

Sample Input 2:

3
1 9 5

Sample Output 2:

Hint 1

Hint 2

How can you find two heaviest stones? If you get the two heaviest stones, which data structure should be preferred to remove them and add their absolute difference in weight if it is non-zero?

Approaches (2)

Approach 1

Approach 2

Removing From List

We will store the stones in a vector/list and run a while loop until the size of the vector/list is greater than 1

Find the index and weight of the two heaviest stones
Remove those stones from the vector/list using their index
Add their absolute difference to the vector/list if the absolute difference is greater than 0

Time Complexity

O(N ^ 2), where N is the total number of stones we have in the beginning.

The number of stones is N and so the first loop will run at most N times, to find the two heaviest stones it will take O(N), and to remove the two heaviest stones it will again take O(N). Adding another stone if weight > 0 will cost again O(N) time. So the overall time complexity is O(N * (N + N + N)) or O(N ^ 2)

Space Complexity

O(1).

Since we are using constant extra space.

(100% EXP penalty)

Last Stone Weight

Console