Quick Overview

Each stone has an integer level, and two stones of the same level can be merged into one stone of the next level, with merged stones able to merge again. Return the fewest stones that can remain after any sequence of merges, a problem that tests counting by level, cascading merges, and efficient handling of large inputs.

Fewest Stones Left After Merging Equal-Level Pairs

Company: Elevenlabs

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Online Assessment

You are carrying a collection of stones, and each stone has a level, which is a positive integer. Two stones with the same level `x` can be merged into one new stone of level `x + 1`. You may perform any number of merges in any order, and a stone created by a merge can itself be merged again. Return the smallest number of stones you can be left with. ### Function Signature ```python def magic(stones: list[int]) -> int: ``` `stones[i]` is the level of the `i`-th stone. ### Rules - A merge always takes exactly two stones of equal level and replaces them with one stone whose level is one higher. Stones of different levels can never be merged. - Merged stones may reach level 10000 or higher; there is no upper limit on the level of a merged stone. - Return the number of stones that remain, not their levels. ### Constraints - `1 <= len(stones) <= 10^5` (the original states only that the list contains at least one stone; the upper bound is assumed for this practice version) - `1 <= stones[i] <= 9999` - The answer is always between `1` and `len(stones)`. ### Examples **Example 1** ```text Input: stones = [1, 2, 1] Output: 1 ``` The two level-1 stones merge into a level-2 stone, and the two level-2 stones then merge into a single level-3 stone. **Example 2** ```text Input: stones = [3, 3, 3] Output: 2 ``` Two of the level-3 stones merge into a level-4 stone. The remaining level-3 stone and the level-4 stone have different levels, so two stones remain. **Example 3** ```text Input: stones = [5, 2, 4, 2, 3] Output: 1 ``` The two level-2 stones merge into level 3, the two level-3 stones into level 4, the two level-4 stones into level 5, and the two level-5 stones into a single level-6 stone.

Overview: Each stone has an integer level, and two stones of the same level can be merged into one stone of the next level, with merged stones able to merge again. Return the fewest stones that can remain after any sequence of merges, a problem that tests counting by level, cascading merges, and efficient handling of large inputs.

Read the full Elevenlabs Software Engineer interview experience this question came from

You are carrying a collection of stones, and each stone has a level, which is a positive integer. `stones[i]` is the level of the `i`-th stone. Two stones with the same level `x` can be merged into one new stone of level `x + 1`. You may perform any number of merges in any order, and a stone created by a merge can itself be merged again. Implement `magic(stones)` to return the smallest number of stones you can be left with. ### Rules - A merge always takes exactly two stones of equal level and replaces them with one stone whose level is one higher. Stones of different levels can never be merged. - Any two stones of equal level can be merged, wherever they appear in `stones`. - Merged stones may reach level 10000 or higher; there is no upper limit on the level of a merged stone. - Return the number of stones that remain, not their levels. ### Constraints - `1 <= len(stones) <= 10^5` - `1 <= stones[i] <= 9999` - The answer is always between `1` and `len(stones)`, so it fits in a 32-bit signed integer in every language. ### Example 1 ```text Input: stones = [1, 2, 1] Output: 1 ``` The two level-1 stones merge into a level-2 stone, and the two level-2 stones then merge into a single level-3 stone. ### Example 2 ```text Input: stones = [3, 3, 3] Output: 2 ``` Two of the level-3 stones merge into a level-4 stone. The remaining level-3 stone and the level-4 stone have different levels, so two stones remain.

Constraints

  • 1 <= len(stones) <= 10^5
  • 1 <= stones[i] <= 9999
  • Merged stones may reach level 10000 or higher; there is no upper limit on the level of a merged stone
  • The answer is always between 1 and len(stones)

Examples

Input: ([1, 2, 1],)

Expected Output: 1

Explanation: Source Example 1: the two level-1 stones make a level-2 stone that re-merges with the existing level-2 stone into one level-3 stone.

Input: ([3, 3, 3],)

Expected Output: 2

Explanation: Source Example 2: an odd count at one level leaves one level-3 stone and one level-4 stone.

Hints

  1. Merges can happen in any order and any two stones of equal level can merge, so think about which information about the input actually matters.
  2. A stone created by a merge can merge again, so a single merge at a low level can trigger further merges higher up.
  3. Ask what stays the same no matter which merges you perform; it limits how few stones can remain.

Loading coding console...

Show the approach

Approach

Approach: only the number of stones at each level matters. Count the stones per input level (levels 1 to M = 9999), then sweep the levels upward with a carry. At level L there are total = count[L] + carry stones; pairing them leaves total mod 2 stones at L and sends floor(total / 2) new stones up to level L + 1. After level 9999 there are no input stones, so the remaining carry is a pile at level 10000 that keeps halving upward with no cap; each level it passes keeps (carry mod 2) stones. The answer is the sum of all leftovers.

Invariant and correctness: give each stone the weight 2^level. A merge replaces two stones of weight 2^x by one of weight 2^(x+1), so the total weight W never changes. Adding one power of two to a number raises its count of set bits by at most one, so any k stones with total weight W satisfy k >= popcount(W): no merge order can leave fewer than popcount(W) stones. The sweep ends with at most one stone per level, which is exactly the binary representation of W, i.e. popcount(W) stones, so it reaches the minimum and the answer is unique. W has about 10,000 bits, so the algorithm never builds it and only tracks per-level counts.

Edge cases: a single stone (answer 1); all stones at one level (the answer is the number of set bits of that count); distinct levels (no merge, answer len(stones)); stones at 9999 whose merges continue past level 10000, handled by the final carry loop; input order is irrelevant because only counts are used. Every per-level total is at most len(stones) <= 10^5, so 32-bit integers suffice in Java and C++.

Time complexity:
O(n + M), where n = len(stones) and M = 9999 is the largest input level
Space complexity:
O(M)