Skip to content

Instantly share code, notes, and snippets.

@Thiruppathi
Created June 9, 2018 12:48
Show Gist options
  • Save Thiruppathi/d5588c81e2948a98d7f80004677f62a7 to your computer and use it in GitHub Desktop.
Save Thiruppathi/d5588c81e2948a98d7f80004677f62a7 to your computer and use it in GitHub Desktop.
/* Missing Integer - Codility
This is a demo task.
Write a function:
function 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.
Assume that:
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].
Complexity:
expected worst-case time complexity is O(N);
expected worst-case space complexity is O(N) (not counting the storage required for input arguments).
*/
function solution(A) {
A.sort(comparator);
return A.reduce((prev, next) => {
if (next > -1 && next === prev) {
prev++;
}
return prev;
}, 1);
}
// Sort the array explicit way
function comparator(a, b) {
return a - b;
}
console.log(solution([1, 3, 6, 4, 1, 2])); // 5
console.log(solution([1, 2, 3])); // 4
console.log(solution([-1, -3])); // 1
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment