[Codility] Lesson-04.3: MissingInteger
2 min readSep 27, 2020
Finding the missing value in a given array is handled in this post. The problem definition can be confirmed via the following URL.
Task Description
This is a demo task.
Write a function:
def solution(A)
that, given an array A of N integers, returns the smallest positive integer (greater than 0) that does not occur in A.
For example, given A = [1, 3, 6, 4, 1, 2], the function should return 5.
Given A = [1, 2, 3], the function should return 4.
Given A = [−1, −3], the function should return 1.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..100,000];
- each element of array A is an integer within the range [−1,000,000..1,000,000].
Copyright 2009–2020 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Key Point
- Applying the sorting algorithm before searching the missing value may give efficiency.
- Some tricky conditional operations, for return the answer directly, prior to conduct linear searching make avoid unnecessary work. It means that gives efficiency.
Solution (using Python)
def solution(A):
A.sort()
if(A[-1] <= 0): return 1 # Trick-1
try: _ = A.index(1) # Trick-2
except: return 1
int_min = A[-1] + 1
for idx in range(len(A)-1):
if(A[idx] <= 0 or A[idx+1] <= 0): continue
if(abs(A[idx] - A[idx+1]) > 1):
int_min = min(int_min, A[idx] + 1)
break
return int_min- Trick-1: When the last value of the array is in the negative area (after sorting the array), that means all the elements are negative value. Thus, you can return 1 directly without any operation.
- Trick-2: The smallest value among the positive integers is 1. If the array includes a larger positive value but does not includes 1, the return value is 1 by exception handling.
Please use the above solution for reference.
I recommend you to write your own source code.
