--- ## Solution Implement the missing code, denoted by ellipses. You may not modify the pre-existing code.
You've just started to study impartial games, and came across an interesting theory. The theory is quite complicated, but it can be narrowed down to the following statements: solutions to all such games can be found with the mex function. Mex is an abbreviation of minimum excludant: for the given set s it finds the minimum non-negative integer that is not present in s.
You don't yet know how to implement such a function efficiently, so would like to create a simplified version. For the given set s and given an upperBound, implement a function that will find its mex if it's smaller than upperBound or return upperBound instead.
Hint: for loops also have an else clause which executes when the loop completes normally, i.e. without encountering any breaks
Example
-
For
s = [0, 4, 2, 3, 1, 7]andupperBound = 10,
the output should be
solution(s, upperBound) = 5.5is the smallest non-negative integer that is not present ins, and it is smaller thanupperBound. -
For
s = [0, 4, 2, 3, 1, 7]andupperBound = 3,
the output should be
solution(s, upperBound) = 3.The minimum excludant for the given set is
5, but it's greater thanupperBound, so the output should be3.
Input/Output
-
[execution time limit] 4 seconds (py3)
-
[input] array.integer s
Array of distinct non-negative integers.
Guaranteed constraints:
0 ≤ s.length ≤ 100,
0 ≤ s[i] ≤ 100. -
[input] integer upperBound
A positive integer.
Guaranteed constraints:
1 ≤ upperBound ≤ 100. -
[output] integer
Mex of
sif it's smaller thanupperBound, orupperBoundinstead.
def solution(s, upperBound):
found = -1
for i in range(upperBound):
if not i in s:
found = i
break
else:
for i in range (0,upperBound):
if not i in s:
return i
return upperBound
return found