Created
June 9, 2018 12:48
-
-
Save Thiruppathi/d5588c81e2948a98d7f80004677f62a7 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* 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