I am trying to create a method add that adds elements x to the set one by one and returns MEX (=minimum non-negative number not in the set) of the list at each point.
class Mex:
def __init__(self):
self.mex = set()
def add(self, x):
self.mex.add(x)
mex = 0
while mex in self.mex:
mex += 1
return mex
This is not efficient enough and it’s probably because the set changes each time. I have also tried the following but the problem is the same
def add(self,x):
self.mex.add(x)
for i in range(len(self.mex)):
if i not in self.mex:
return i
return len(self.mex)
Tips?
>Solution :
Don’t always start from 0 again, remember where you were.
class Mex:
def __init__(self):
self.added = set()
self.mex = 0
def add(self, x):
self.added.add(x)
while self.mex in self.added:
self.mex += 1
return self.mex