0. Introduction
A) Languages allowed
The Codility skills assessment demo test allows for solutions
written in 18 different languages: C, C++, C#, Go, Java 8, Java 11, JavaScript, Kotlin, Lua, Objective-C, Pascal, PHP, Perl, Python, Ruby, Scala, Swift 4, Visual Basic.
B) Some remarks on your question
I write the solution below which gives a low performance
There is no reason to worry about performance until you have a
correct solution.
Always make sure the solution is correct before you even think about
how fast or slow your algorithm/code is!
expected worst-case time complexity is O(N)
Well, as the asker of the question, it is your decision what
requirements should be met in an answer.
But if the goal is to score 100% in the Codility (performance) test,
then there is no need to demand O(N).
There are plenty of solutions in the answers here which are O(N log N)
and not O(N), but still pass all 4 performance tests.
This proves that the O(N) requirement on time complexity is
unnecessarily harsh (if the sole aim is to score 100% on the Codility
test).
C) About the solutions presented here
All of the solutions presented here are either refactored versions of
already published answers, or inspired by such answers.
All solutions here score 100% in the Codility skills assessment
demo test.
1
I have striven to
- explicitly reference each original answer/solution,
- provide a runnable jdoodle link for each
solution,
- use the same 8 tests (chosen by myself) for all the solutions,
- choose solutions that score 100% (meaning 5 of 5 for correctness and
4 of 4 for performance/speed),
- make it easy to copy-paste the answers directly into the Codility
skills assessment demo test,
- focus on some of the most used languages.
1. Java: the Codility test for correctness is incorrect (!)
I will use one of the existing answers to demonstrate that the Codility
test for correctness is flawed for the edge case when the given array
is empty.
In an empty array, the smallest positive missing integer is clearly 1.
Agreed?
But the Codility test suite seems to accept just about any answer for
the empty array.
In the code below, I deliberately return -99 for the empty array,
which is obviously incorrect.
Yet, Codility gives me a 100% test score for my flawed solution. (!)
import java.util.Arrays;
/**
https://app.codility.com/demo/take-sample-test 100%
https://stackoverflow.com/a/57067307
https://jdoodle.com/a/3B0D
To run the program in a terminal window:
javac Solution.java && java Solution && rm Solution.class
Terminal command to run the combined formatter/linter:
java -jar ../../../checkstyle-8.45.1.jar -c ../../../google_checks.xml *.java
*/
public class Solution {
/** Returns the smallest positive integer missing in intArray. */
public static int solution(int[] intArray) {
if (intArray.length == 0) { // No elements at all.
return -99; // So the smallest positive missing integer is 1.
}
Arrays.sort(intArray);
// System.out.println(Arrays.toString(intArray)); // Temporarily uncomment?
if (intArray[0] >= 2) { // Smallest positive int is 2 or larger.
return 1; // Meaning smallest positive MISSING int is 1.
}
if (intArray[intArray.length - 1] <= 0) { // Biggest int is 0 or smaller.
return 1; // Again, smallest positive missing int is 1.
}
int smallestPositiveMissing = 1;
for (int i = 0; i < intArray.length; i++) {
if (intArray[i] == smallestPositiveMissing) {
smallestPositiveMissing++;
} // ^^ Stop incrementing if intArray[i] > smallestPositiveMissing. ^^
} // Because then the smallest positive missing integer has been found:
return smallestPositiveMissing;
}
/** Demo examples. --> Expected output: 1 2 3 4 1 2 3 1 (but vertically). */
public static void main(String[] args) {
System.out.println("Hello Codility Demo Test for Java, B");
int[] array1 = {-1, -3};
System.out.println(solution(array1));
int[] array2 = {1, -1};
System.out.println(solution(array2));
int[] array3 = {2, 1, 2, 5};
System.out.println(solution(array3));
int[] array4 = {3, 1, -2, 2};
System.out.println(solution(array4));
int[] array5 = {};
System.out.println(solution(array5));
int[] array6 = {1, -5, -3};
System.out.println(solution(array6));
int[] array7 = {1, 2, 4, 5};
System.out.println(solution(array7));
int[] array8 = {17, 2};
System.out.println(solution(array8));
}
}
Below is a screen dump of the result from the test.
As the solution is clearly wrong, of course it should not score 100%!
2
2. JavaScript
Below is a JavaScript solution.
This one has not been posted before, but is inspired by
one of the previous answers.
/**
https://app.codility.com/demo/take-sample-test 100%
(c) Henke 2022 https://stackoverflow.com/users/9213345
https://jdoodle.com/a/3AZG
To run the program in a terminal window:
node CodilityDemoJS3.js
Terminal command to run the combined formatter/linter:
standard CodilityDemoJS3.js
https://github.com/standard/standard
*/
function solution (A) {
/// Returns the smallest positive integer missing in the array A.
let smallestMissing = 1
// In the following .reduce(), the only interest is in `smallestMissing`.
// I arbitrarily return '-9' because I don't care about the return value.
A.filter(x => x > 0).sort((a, b) => a - b).reduce((accumulator, item) => {
if (smallestMissing < item) return -9 // Found before end of the array.
smallestMissing = item + 1
return -9 // Found at the end of the array.
}, 1)
return smallestMissing
}
// Demo examples. --> Expected output: 1 2 3 4 1 2 3 1 (but vertically).
// Note! The following lines need to be left out when running the
// Codility Demo Test at https://app.codility.com/demo/take-sample-test :
console.log('Hello Codility Demo Test for JavaScript, 3.')
console.log(solution([-1, -3]))
console.log(solution([1, -1]))
console.log(solution([2, 1, 2, 5]))
console.log(solution([3, 1, -2, 2]))
console.log(solution([]))
console.log(solution([1, -5, -3]))
console.log(solution([1, 2, 4, 5]))
console.log(solution([17, 2]))
.as-console-wrapper { max-height: 100% !important; top: 0; }
3. Python
Python has come to compete with Java as one of the most used
programming languages worldwide.
The code below is a slightly rewritten version of this answer.
#!/usr/bin/env python3
'''
https://app.codility.com/demo/take-sample-test 100%
https://stackoverflow.com/a/58980724
https://jdoodle.com/a/3B0k
To run the program in a terminal window:
python codility_demo_python_a.py
Command in the terminal window to run the linter:
py -m pylint codility_demo_python_a.py
https://pypi.org/project/pylint/
Dito for autopep8 formatting:
autopep8 codility_demo_python_a.py --in-place
https://pypi.org/project/autopep8/
'''
def solution(int_array):
'''
Returns the smallest positive integer missing in int_array.
'''
max_elem = max(int_array, default=0)
if max_elem < 1:
return 1
int_array = set(int_array) # Reusing int_array although now a set
# print(int_array) # <- Temporarily uncomment at line beginning
all_ints = set(range(1, max_elem + 1))
diff_set = all_ints - int_array
if len(diff_set) == 0:
return max_elem + 1
return min(diff_set)
# Demo examples. --> Expected output: 1 2 3 4 1 2 3 1 (but vertically).
# Note! The following lines need to be commented out when running the
# Codility Demo Test at https://app.codility.com/demo/take-sample-test :
print('Hello Codility Demo Test for Python3, a.')
print(solution([-1, -3]))
print(solution([1, -1]))
print(solution([2, 1, 2, 5]))
print(solution([3, 1, -2, 2]))
print(solution([]))
print(solution([1, -5, -3]))
print(solution([1, 2, 4, 5]))
print(solution([17, 2]))
4. C#
Here a solution for C#, inspired by a previous answer.
using System;
using System.Linq;
/// https://app.codility.com/demo/take-sample-test 100%
/// (c) 2021 Henke, https://stackoverflow.com/users/9213345
/// https://jdoodle.com/a/3B0Z
/// To initialize the program in a terminal window, only ONCE:
/// dotnet new console -o codilityDemoC#-2 && cd codilityDemoC#-2
/// To run the program in a terminal window:
/// dotnet run && rm -rf obj && rm -rf bin
/// Terminal command to run 'dotnet-format':
/// dotnet-format --include DemoC#_2.cs && rm -rf obj && rm -rf bin
public class Solution {
/// Returns the smallest positive integer missing in intArray.
public int solution(int[] intArray) {
var sortedSet =
intArray.Where(x => x > 0).Distinct().OrderBy(x => x).ToArray();
// Console.WriteLine("[" + string.Join(",", sortedSet) + "]"); // Uncomment?
if (sortedSet.Length == 0) return 1; // The set is empty.
int smallestMissing = 1;
for (int i = 0; i < sortedSet.Length; i++) {
if (smallestMissing < sortedSet[i]) break; // The answer has been found.
smallestMissing = sortedSet[i] + 1;
} // Coming here means all of `sortedSet` had to be traversed.
return smallestMissing;
}
/// Demo examples. --> Expected output: 1 2 3 4 1 2 3 1 (but vertically).
/// NOTE! The code below must be removed before running the Codility test.
static void Main(string[] args) {
Console.WriteLine("Hello Codility Demo Test for C#, 2.");
int[] array1 = { -1, -3 };
Console.WriteLine((new Solution()).solution(array1));
int[] array2 = { 1, -1 };
Console.WriteLine((new Solution()).solution(array2));
int[] array3 = { 2, 1, 2, 5 };
Console.WriteLine((new Solution()).solution(array3));
int[] array4 = { 3, 1, -2, 2 };
Console.WriteLine((new Solution()).solution(array4));
int[] array5 = { };
Console.WriteLine((new Solution()).solution(array5));
int[] array6 = { 1, -5, -3 };
Console.WriteLine((new Solution()).solution(array6));
int[] array7 = { 1, 2, 4, 5 };
Console.WriteLine((new Solution()).solution(array7));
int[] array8 = { 17, 2 };
Console.WriteLine((new Solution()).solution(array8));
}
}
5. Swift
Here is a solution for Swift, taken from this answer.
/**
https://app.codility.com/demo/take-sample-test 100%
https://stackoverflow.com/a/57063839
https://www.jdoodle.com/a/4ny5
*/
public func solution(_ A : inout [Int]) -> Int {
/// Returns the smallest positive integer missing in the array A.
let positiveSortedInts = A.filter { $0 > 0 }.sorted()
// print(positiveSortedInts) // <- Temporarily uncomment at line beginning
var smallestMissingPositiveInt = 1
for elem in positiveSortedInts{
// if(elem > smallestMissingPositiveInt) then the answer has been found!
if(elem > smallestMissingPositiveInt) { return smallestMissingPositiveInt }
smallestMissingPositiveInt = elem + 1
}
return smallestMissingPositiveInt // This is if the whole array was traversed.
}
// Demo examples. --> Expected output: 1 2 3 4 1 2 3 1 (but vertically).
// Note! The following lines need to be left out when running the
// Codility Demo Test at https://app.codility.com/demo/take-sample-test :
print("Hello Codility Demo Test for Swift 4, A.")
var array1 = [-1, -3]
print(solution(&array1))
var array2 = [1, -1]
print(solution(&array2))
var array3 = [2, 1, 2, 5]
print(solution(&array3))
var array4 = [3, 1, -2, 2]
print(solution(&array4))
var array5 = [] as [Int]
print(solution(&array5))
var array6 = [1, -5, -3]
print(solution(&array6))
var array7 = [1, 2, 4, 5]
print(solution(&array7))
var array8 = [17, 2]
print(solution(&array8))
6. PHP
Here a solution for PHP, taken from this answer.
<?php
/**
https://app.codility.com/demo/take-sample-test 100%
https://stackoverflow.com/a/60535808
https://www.jdoodle.com/a/4nB0
*/
function solution($A) {
$smallestMissingPositiveInt = 1;
sort($A);
foreach($A as $elem){
if($elem <=0) continue;
if($smallestMissingPositiveInt < $elem) return $smallestMissingPositiveInt;
else $smallestMissingPositiveInt = $elem + 1;
}
return $smallestMissingPositiveInt;
}
// Demo examples. --> Expected output: 1 2 3 4 1 2 3 1 .
// Note! The starting and ending PHP tags are needed when running
// the code from the command line in a *.php file, but they and
// the following lines need to be left out when running the Codility
// Demo Test at https://app.codility.com/demo/take-sample-test :
echo "Hello Codility Demo Test for PHP, 1.\n";
echo solution([-1, -3]) . " ";
echo solution([1, -1]) . " ";
echo solution([2, 1, 2, 5]) . " ";
echo solution([3, 1, -2, 2]) . " ";
echo solution([]) . " ";
echo solution([1, -5, -3]) . " ";
echo solution([1, 2, 4, 5]) . " ";
echo solution([17, 2]) . " ";
?>
References
1
This is true even for the first solution – the Java solution –
despite the the fact that this solution is wrong!
2 You can try running the test yourself at
https://app.codility.com/demo/take-sample-test.
You will have to sign up to do so.
Simply copy-paste all of the code from the snippet.
The default is Java 8, so you won't need to change the language
for the first solution.
