Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /**
- * Write a function that, given an array A of N integers, returns the smallest positive integer (greater than 0) that does not occur in A. <br/>
- * For example, given <code>A = [1, 3, 6, 4, 1, 2]</code>, the function should return 5. <br/>
- * Given <code>A = [1, 2, 3]</code>, the function should return 4. <br/>
- * Given <code>A = [-1, -3]</code>, the function should return 1. <br/>
- * <br/>
- * Write an efficient algorithm for the following assumptions: <br/>
- * N is an integer within the range <code>[1..100,000]</code>. <br/>
- * Each element of array A is an integer within the range <code>[-1,000,000..1,000,000]</code>. <br/>
- * <br/>
- * Max time for resolution: 30 minutes.
- */
- class SmallestPositiveIntegerNotOccurring {
- public static void main(String[] args) {
- SmallestPositiveIntegerNotOccurring solution = new SmallestPositiveIntegerNotOccurring();
- System.out.println(solution.solution(new int[] {1, 3, 6, 4, 1, 2})); // 5
- System.out.println(solution.solution(new int[] {1, 2, 3})); // 4
- System.out.println(solution.solution(new int[] {-1, -3})); // 1
- System.out.println(solution.solution(new int[] {-1000000, 1000000})); // 1
- }
- public int solution(int[] A) {
- // check corner cases
- if (A == null || A.length == 0) {
- return 1;
- }
- // Each element of array A is an integer within the range [−1,000,000..1,000,000].
- // We are going to keep track only of positive numbers we have visited
- boolean[] visitedPositives = new boolean[1000000 + 1]; // initialized by the JVM with false
- // traverse all target array and keep track of positive integers
- for (int i=0, c=A.length; i < c; ++i) {
- // get current number
- int current = A[i];
- // keep track of visited positive numbers
- if (current > 0) {
- visitedPositives[current] = true;
- }
- }
- // traverse visited positive numbers array and keep the index > 0 of the first position marked as false
- for (int i=1, c=visitedPositives.length; i < c; i++) {
- if (!visitedPositives[i]) {
- return i;
- }
- }
- // fallback: all positive numbers exist in the A array
- return 10000001;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement