[Codility Lessons] Perm Missing Elem

N 길이의 배열에 1부터 N+1만큼의 요소가 포함됩니다. 이때 배열에서 빠진 숫자를 구하는 함수를 작성하는 문제입니다.

예를 들어, 길이가 4인 배열에 1부터 5 사이의 숫자가 들어갑니다.
(숫자들은 순서대로 정렬되어 있지 않을 수 있습니다.)
[2, 3, 1, 5] 이 중에서 빠진 숫자는 4입니다.

function solution(A) {
  // 빈 배열일 경우 1을 리턴합니다.
  if (A.length === 0) return 1;
  
  // 1부터 N+1만큼의 배열을 만들어 줍니다.
  // N의 범위가 100,000이기 때문에 가능한 방법이라고 생각합니다.
  // 만약에 더 큰 범위라면 시간복잡도와 관련해 효율적이지 않습니다.
  const nums = Array(A.length + 1).fill(0);
  
  // 생성한 배열에 A의 숫자를 대입합니다.
  for (let i = 0; i < A.length; i++) {
    nums[A[i] - 1] = A[i];
  }
  
  // 배열에서 0값을 가진 인덱스를 리턴합니다.
  return nums.indexOf(0) + 1;
}

처음에는 위와 같이 풀었는데, 다른 풀이를 참고하여,
배열의 N+1까지 더한 값에서
A 배열의 값을 모두 더해 빼주는 방법이 있는 걸 알게 되었습니다.

function solution(A) {
  if (A.length === 0) return 1;
  const arrSum = A.reduce((acc, cur) => acc + cur);
  let numSum = 0;

  for (let i = 1; i <= A.length + 1; i++) {
    numSum += i;
  }

  return numSum - arrSum;
}

두가지 방법 모두 O(N) 또는 O(N*log(N))의 시간복잡도를 가집니다.