[GO] [100%] PermMissingElem (src & jUnit)

Painless

PermMissingElem

Find the missing element in the specified permutation.

Task description

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:

• N is an integer in the range [0..100,000].
• All elements of A are separate.
• Each element of array A is an integer in the range [1 .. (N + 1)].

solve

Program [Proposal 1: Arrays.sort]

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

Program [Proposal 2: data bucket]

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