Lesson 3 - PermMissingElem

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개의 다른 숫자를 가진 배열이 1.. N+1 범위의 중복되지 않는 랜덤한 숫자를 가지고 있을때 그 중 빠진 숫자를 찾는 문제이다. (내가 적었지만 영어라서 바로 이해하기가 조금 어려웠다.)

정렬 시키고 index에 1 더한 값이 현재 인덱스 위치 값과 같지 않을 경우, 바로 리턴시켰다.

길이가 하나이거나, 혹은 빠진 숫자가 맨 처음 혹은 뒤에 있을 때 케이스에서 찾을 수 없어 애를 먹었었다. 마지막에 길이+1 시켜 이를 해결하였다.

import java.util.Arrays;

class Solution {
    public int solution(int[] A) {
        Arrays.sort(A);

        for(int i=0; i<A.length; i++) {
            if((i+1) != A[i]) return i + 1; 
        }

        return A.length + 1;
    }
}