Fewest Stones Left After Merging Equal-Level Pairs

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

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

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

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

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.

Fewest Stones After Merging Equal Levels

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

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

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.

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.

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)