[Codility] [Javascript] PermMissingElem

Task description

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:

function solution(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)].

 

 

---

 

 

 

📢 첫 번째 시도는 55점이었다. 약간 아무래도 깊이 생각 안하는 서타일인듯.....

기본적인 테스트는 통과했지만 큰 숫자들에서 전부 2를 뱉어내고 있었다.

 

알고리즘을 풀때 보통 반복문 & 조건문만을 이용하여 단편적으로 짜곤 했는데

시간 복잡도와 여러 가지 정확성을 고려했을 땐 마냥 좋은 방법은 아닌듯 하다.

 

 

---

 

🌈 PermMissingElem.js

function solution(A) {
    const arrLength = A.length;
 
    // 빈 배열일 경우 1 리턴
    if (arrLength === 0) {
        return 1;
    } else {
        // 연속된 수의 합 공식 이용
        const realSum = ((arrLength+1) * (arrLength+2)) / 2;
        const missingSum = A.reduce((sum, e) => sum + e, 0);
 
        return realSum - missingSum;
    }
}

 

🔸 그래서 중학교 때 배웠던 합 공식을 생각해냈다.

배열에는 1개의 숫자만 누락되어 있으므로, 1부터 배열 크기 + 1 까지 더해주고,

배열 속 element들을 모두 더한 값을 빼면 누락된 수 1개가 도출된다.

 

 

 

 

 

👩‍💻 풀어보기 👨‍💻 https://app.codility.com/programmers/lessons/3-time_complexity/perm_missing_elem/start/

Codility