[Codility] 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.

• 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)].

 

가장 간단하게 생각할 수 있는 알고리즘은 이중 for 문을 이용해 A의 각 원소들과 1~(N+1)을 비교해 없는 값을 return하는 알고리즘이다. 

하지만 그 알고리즘은 O(N^2) 이기 때문에 더 쉬운 방법을 생각해보았다.

 

그 방법은 ∑(1~(N+1)) - ∑(A[i]) 이다. 즉, 1 ~ (N+1) 중 A 에 없는 원소만큼의 차이가 벌어진다는 개념에서 착안한 알고리즘이다. 

이 때의 시간 복잡도는 O(N) 이다.

 

문제를 해결할 때, 중요한 조건으로 생각한부분은 N = 0일때이다.

 N = 0 일때는  A = [ ] 가 들어오고 이 배열이 가져야할 원소의 범위는 [ 1 ~ 1 ] 이므로 빠진 값은 1 이다.

따라서 밑의 코드로 문제없이 계산이 되는것을 알 수 있다.

 

class Solution {
    public int solution(int[] A) {
        
        int sumAll = 0;
        int sumA = 0;
        
        for(int i=1; i<=(A.length+1); i++){
            sumAll += i;
            
            if(i != A.length+1){
                sumA += A[i-1];    
            }
        }
        
        return (sumAll - sumA);
    }
}