[Codility - Java] 3. Time Complexity - 2. PermMissingElem

PermMissingElem

Find the missing element in a given permutation.

An array A consisting of N different integers is given. The array contains integers in the range [1..(N + 1)], which means that exactly one element is missing.

Your goal is to find that missing element.

Write a function:

class Solution { public int solution(int[] A); }

that, given an array A, returns the value of the missing element.

For example, given array A such that:

A[0] = 2
A[1] = 3
A[2] = 1
A[3] = 5

the function should return 4, as it is the missing element.

Write an efficient algorithm for the following assumptions:

• N is an integer within the range [0..100,000];
• the elements of A are all distinct;
• each element of array A is an integer within the range [1..(N + 1)].

---

N 개의 서로다른 정수로 구성된 배열 A
배열의 각 요소는 $1 <= A[i] <= N + 1$ 범위 중 하나고,
단 하나의 정수만 없다.

배열 안에서 빠져있는 정수를 리턴하는 코드를 작성하면 됩니다.

배열 A를 순회하며 arr에 넣은 후,
arr를 다시 순회하면서 값이 들어있지 않은 경우 그 값을 리턴하면 됩니다.

int result = 0;
int[] arr = new int[A.length + 2];
for (int a : A) {
    arr[a] = 1;
}
for (int i = 1; i < arr.length; i++) {
    if (arr[i] == 0) {
       result = i;
       break;
    }
}
return result;

$O(N)$ or $O(N * log(N))$