Java solution to Codility PermMissingElem (Permutation Missing Element) problem (Lesson 3 – Time Complexity) which scored 100%. The problem is to find the missing element in a given permutation. The main strategy is use a HashSet to store elements which will also order them. Then check all values from 1 to max to see if it’s missing from HashSet.
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.util.HashSet;
import java.util.Set;
public class PermutationMissingElement {
public int solution(int[] A) {
int max = A.length + 1;
//load array elements into array so would be quick to check if elements exist
Set incompleteSet = new HashSet();
for(int i=0; i<A.length; i++) {
incompleteSet.add(A[i]);
}
for(int i=1; i<max+1; i++) {
if(!incompleteSet.contains(i)) {
return (i);
}
}
throw new RuntimeException("shouldn't reach here");
}
}
TestNG test cases for this problem which all passed:
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import org.testng.Assert;
import org.testng.annotations.*;
import com.codility.lesson03.timecomplexity.PermutationMissingElement;
public class PermutationMissingElementTests {
private PermutationMissingElement solution;
@BeforeTest
public void setUp() {
solution = new PermutationMissingElement();
}
@DataProvider(name = "test1")
public Object [][] createData1() {
return new Object [][] {
new Object [] { new int [] { }, 1 },
new Object [] { new int [] { 1 }, 2 },
new Object [] { new int [] { 2 }, 1 },
new Object [] { new int [] { 1, 3 }, 2 },
new Object [] { new int [] { 2, 3 }, 1 },
new Object [] { new int [] { 1, 2 }, 3 },
new Object [] { new int [] { 1, 3, 4 }, 2 },
new Object [] { new int [] { 2, 4, 3 }, 1 },
new Object [] { new int [] { 2, 3, 1, 5 }, 4 },
new Object [] { new int [] { 4, 2, 3, 1, 5, 6, 8, 9 }, 7 },
new Object [] { new int [] { 4, 2, 3, 1, 5, 6, 8, 7 }, 9 },
};
}
@Test(dataProvider = "test1")
public void verifySolution(int [] pA, int pExpectedMissingValue) {
Assert.assertEquals(solution.solution(pA), pExpectedMissingValue);
}
}