Given a collection of stones, each stone has a positive integer weight. 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 is:
If x == y, both stones are totally destroyed.
If x != y, the stone of weight x is totally destroyed, and the stone of weight y has new weight y-x.
At the end, there is at most 1 stone left. Return the weight of this stone (or 0 if there are no stones left.)
For Example –
Input: {2, 7, 4, 1, 8, 1}, Output: 1
Explanation:
We combine 7 and 8 to get 1 so the array converts to {2, 4, 1, 1, 1} then,
we combine 2 and 4 to get 2 so the array converts to {2, 1, 1, 1} then,
we combine 2 and 1 to get 1 so the array converts to {1, 1, 1} then,
we combine 1 and 1 to get 0 so the array converts to {1} then that’s the value of last stone.
Programming Questions on Arrays
Programming Questions on Linked List
Programming Questions on String
Last Stone Weight – Java Code
To solve this problem, what we have to do is to remove the two heaviest stones, and then we have to calculate their difference. After that put their difference back. We have to repeat this process until one or zero element is left.
So, We need a data structure from which we get the max element at the top (out of all the elements). So that every time we poll them we get the max weight.
Here, I am going to use Priority queue to solve this problem.
The time complexity of this approach is O(nlogn) and it’s space complexity is O(n).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
//Last stone weight - Java Code public class LastStoneWeight { public static int lastStoneWeight(int[] stones) { /* Collections.reverseOrder() is used to reverse the natural ordering. So that we get the max element at the top of the priority queue. */ PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder()); for (Integer stone : stones) { pq.add(stone); } while (pq.size() > 1) { pq.add(pq.poll() - pq.poll()); } return pq.peek(); } public static void main(String[] args) { int[] arr = {2, 7, 4, 1, 8, 1}; int result = lastStoneWeight(arr); System.out.println(result); } |
