Painless
PermMissingElem
Find the missing element in the specified permutation.
Given an array A consisting of N different integers. The array contains integers in the range [1 .. (N + 1)]. This means that one element is missing.
Your goal is to find that missing element.
Write a function:
class solution {public int solution(int [] A); }
Given array A, returns the value of the missing element.
For example, given the following array A:
A [0] = 2
A [1] = 3
A [2] = 1
A [3] = 5
The function must return 4 because it is a missing element.
Write an efficient algorithm for the following assumptions:
PermMissingElemSolutionSort.java
PermMissingElemSolutionSort.java
public int solution(int[] A) {
if (A.length == 0) return 1;
java.util.Arrays.sort(A);
for (int i = 0; i < A.length; i++) {
if ((i + 1) != A[i]) return i + 1;
}
return A.length + 1;
}
Detected time complexity:
O(N) or O(N * log(N))
jUnit PermMissingElemSolutionSortTest.java
PermMissingElemSolutionBucket.java
PermMissingElemSolutionBucket.java
public int solution(int[] A) {
boolean[] bucket = new boolean[100000 + 2];
java.util.Arrays.fill(bucket, false);
for (int anA : A) {
bucket[anA] = true;
}
for (int i = 1; i < bucket.length; i++) {
if (!bucket[i]) {
return i;
}
}
return 1;
}
Detected time complexity:
O(N) or O(N * log(N))
jUnit PermMissingElemSolutionBucketTest.java
Recommended Posts