Codility ‘MissingInteger’ Solution
1 min readNov 13, 2021
I came across another interesting coding problem on Codility and wanted to share my learnings.
Problem
Find the smallest positive integer (>0) not occurring in a given sequence. Link to the full problem (Lesson 4 — Counting Elements).
Solution in Python
I’ve scored 100% for this solution
def solution(A):
num_set = set(A)
min_num = 1
while min_num in num_set:
min_num+=1
return min_num#testcase1, expect 5
solution([1, 3, 6, -4, 1, 2,-3])#testcase2, expect 4
solution([1, 2, 3])#testcase3, expect 1
solution([-2, -4])
- I created a set of array A to avoid re-checking duplicates.
- I have set min_num = 1. If 1 is not found in the array, it is returned immediately as it’s the lowest possible positive integer. As seen in test case #3, we will return 1 straight.
- If 1 is found in the array, then we will iteratively add 1 and check if it’s in the num_set. This will ensure that we return the lowest possible number.
- The worst case time-complexity would be O(n) if we have to iterate to the end of the list, as seen in test case #2.
Hope it helps! :)
If you found this article helpful, I would really appreciate if you could follow my account and give this article a clap! Thank you!! :D