Katkat
Back

Fewest Stones Left After Merging Equal-Level Pairs

ElevenlabsSoftware Engineer · Online Assessment
MediumSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

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.

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.