Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Heap & Priority Queue

Last Stone Weight

Easy · Heap & Priority Queue · Asked at Amazon, Google, Microsoft

Each turn, take the two heaviest stones x ≤ y and smash them: if x = y both are destroyed, otherwise the y stone becomes y − x. Continue until at most one stone is left. Print its weight, or 0 if no stone remains.

Input

First line: n. Second line: n space-separated integers.

Output

The weight of the last stone, or 0.

Constraints

A max-heap gives the two heaviest stones in O(log n).

Example 1

Input

6
2 7 4 1 8 1

Output

1

Example 2

Input

2
5 5

Output

0

Hints

  1. You always need the two heaviest stones — a max-heap.
  2. Pop two; if they differ, push the difference back. Repeat while at least two stones remain.

Approach

Put all stones in a max-heap. While it holds two or more, pop y (heaviest) and x; if y > x, push y − x. When one stone is left print it; when none, print 0. (Python's heapq is a min-heap, so store negated weights.)

Complexity: O(n log n) time · O(n) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    priority_queue<int> pq;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        pq.push(x);
    }
    while (pq.size() > 1) {
        int y = pq.top();
        pq.pop();
        int x = pq.top();
        pq.pop();
        if (y > x) pq.push(y - x);
    }
    cout << (pq.empty() ? 0 : pq.top()) << "\n";
    return 0;
}

Python solution

import sys
import heapq

data = list(map(int, sys.stdin.read().split()))
heap = [-x for x in data[1:]]
heapq.heapify(heap)
while len(heap) > 1:
    y = -heapq.heappop(heap)
    x = -heapq.heappop(heap)
    if y > x:
        heapq.heappush(heap, -(y - x))
print(-heap[0] if heap else 0)

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        for (int i = 0; i < n; i++) pq.add(sc.nextInt());
        while (pq.size() > 1) {
            int y = pq.poll(), x = pq.poll();
            if (y > x) pq.add(y - x);
        }
        System.out.println(pq.isEmpty() ? 0 : pq.peek());
    }
}

Solve Last Stone Weight online · All practice problems