[Codility] Time Complexity - PermMissingElem 풀이
예문
https://app.codility.com/programmers/lessons/3-time_complexity/perm_missing_elem/
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)].
해석
- 배열 A : N개의 서로 다른 정수로 구성
- 배열 A : [1..(N + 1)]의 범위로 구성
- 1로 시작하기 때문에 한 개의 누락된 요소 발생
- 누락된 요소를 리턴하라!
풀이
- 누적합 공식 사용 : (시작숫자 + 끝숫자 ) * 끝숫자 / 2
제약사항
- N의 범위는 정수 [0..100,000]
- A의 모든 요소는 중복되지 않는다.
- A의 각 요소의 범위는 정수 [1..(N + 1)]
코드
public int solution(int[] A) {
long lastNum = A.length + 1;
long sum = 0;
for (int n : A) {
sum += n;
}
return (int)((1 + lastNum) * lastNum / 2 - sum);
}