Minimum Hits Needed

Fewest Hits Required

You are given an integer array targets, with each value indicating how much durability a target has before it is eliminated. A single range hit may fully remove targets only if the targets included in that hit currently have identical durability. Determine the smallest number of hits required to eliminate every target.

Input:

• An integer array targets, where each entry gives one target's durability.

Output:

• A single integer: the minimum number of hits necessary to destroy every target.

Example:

Input: targets = [4, 4, 2, 5]

Output: 3

Explanation: One possible sequence of hits is:

1. On the first hit, choose range [0, 1]; the targets [4, 4] are destroyed.
2. On the second hit, choose range [2, 2]; the target [2] is destroyed.
3. On the third hit, choose range [3, 3]; the target [5] is destroyed.

Constraints:

• 1 <= targets.length <= 10^5
• 1 <= targets[i] <= 10^9

Example

Input: [6, 6, 1, 8]
Output: 3