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.

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

  Copyright 2009–2020 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

 

---

 

N개의 다른 정수를 포함한 하나의 A 배열이 주어지고, 

A 배열은 1 ~ N+1개의 정수 범위내에서 값을 가질수 있다. 

 

배열에서 빠진 하나의 숫자를 찾아라!! 

 

---

생각할 시간

 

1. 같은 크기의 배열을 생성하고 원본 배열을 for 문을 돌려 각 요소의 값에 해당하는 배열에 위치시키면 어떨까??

2. 해봄.. 땡! 성능도 안좋았을 뿐더러 오답도 존재함. 

 

놓친부분. empty array 일 경우엔 return 값이 1이 되어야함. 왜냐! 배열의 값은 1 ~ N+1의 값 내에 존재해야하니까. 

 

3. Arrays.sort()를 이용해 배열을 정렬시키고 다시 위 작업을 보완하면 어떨까? 땡!! 효과 없음. 머리가 굳음. 

 

4. A 배열의 값은 1 ~ N+1의 값만 가질 수 있음. 

   즉, N = 4 -> 1,2,3,4,5의 값만 가질수있음. 즉, 빠진값은  1 + 2+ 3+ 4+ 5 - 배열원소의 합이라 생각할 수 있었음.

 

  예제를 통한 시뮬레이션

 

  N = 4 -> (1 + 2 + 3 + 4 + 5) - (2 + 3 + 1 + 5 ) = 4

  N = 3 -> (1 + 2 + 3 + 4) - (1 + 4 + 3) = 2

 

 

 

소스코드 : 

 

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {

    public int solution(int[] A) {
        // write your code in Java SE 8
        
        int N = A.length;
        
        int totalSum = 0;
        int arrSum = 0;
        
        for(int i=0; i < N; i++) {
            
            totalSum += (i+1);
            
            arrSum += A[i];
            
        }
        
        return totalSum - arrSum + N + 1;
        
    }
}

 

결과는 O(N) or O(N * log(N)) 통과