BinarySearch 0686 Deleting Repeated Integers Game

Problem statement

https://binarysearch.com/problems/Deleting-Repeated-Integers-Game/

Solution

It can be shown that answer depends on number of duplicates: we need 1 step if we have 1 or 2, we need 2 steps if we have 3 or 4 and so on.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, nums):
        return (len(nums) - len(set(nums)) + 1)//2