JavaScript 등차수열에서 누락된 숫자 찾기: 한 번의 반복으로 해결하기

등차수열이란?

등차수열(Arithmetic Progression, AP)은 연속된 두 항 사이의 차이, 즉 공차가 항상 일정하게 유지되는 수열을 말합니다.

예를 들어 5, 7, 9, 11, 13... 과 같은 수열은 매번 2씩 증가하므로 대표적인 등차수열입니다.

문제 정의

등차수열의 요소들이 순서대로 담긴 배열이 하나 있다고 가정해 보겠습니다. 그런데 어떤 이유에서인지 수열의 숫자 하나가 누락되어 버렸습니다. 우리는 이 배열을 첫 번째이자 유일한 인수로 받아 처리하는 JavaScript 함수를 작성해야 합니다.

작성할 함수는 단 한 번의 반복만으로 수열에서 빠진 숫자를 찾아 반환해야 합니다.

예를 들어 입력 배열이 다음과 같다면,

const arr = [7, 13, 19, 31, 37, 43];

기대하는 출력 결과는 다음과 같습니다.

const output = 25;

19와 31 사이의 25가 누락되었기 때문입니다.

구현 예제

이 문제를 해결하는 코드는 다음과 같습니다.

const arr = [7, 13, 19, 31, 37, 43];
const findMissingNumber = (arr = []) => {
    let {length} = arr;
    let diff1 = arr[1] - arr[0];
    let diff2 = arr[length - 1] - arr[length - 2];
    if (diff1 !== diff2) {
        if (diff1 == 2 * diff2){
            return arr[0] + diff2;
        }else{
            return arr[length - 1] - diff1;
        };
    };
    for (let i = 1; i < length - 2; i++){
        if (arr[i + 1] - arr[i] != diff1){
            return arr[i] + diff1;
        };
    };
    return arr[0];
};
console.log(findMissingNumber(arr));

출력 결과

코드를 실행하면 콘솔에 다음과 같이 출력됩니다.

코드 작동 원리

공차 후보 비교: 먼저 배열의 첫 두 요소의 차이(diff1)와 마지막 두 요소의 차이(diff2)를 계산합니다.
경계 예외 처리: 두 값이 다르다면 누락된 숫자가 배열의 맨 앞 또는 맨 뒤 근처에 있다는 뜻입니다. diff1이 diff2의 정확히 2배라면 누락된 숫자는 시작 부분 근처(arr[0] + diff2)에 있고, 그렇지 않다면 끝 부분 근처(마지막 요소 − diff1)에 있습니다.
본문 순회: 두 차이가 같다면 그 값이 실제 공차입니다. 이후 배열을 순회하며 인접한 두 요소의 차이가 공차와 다른 지점을 찾으면, 그 자리가 곧 누락된 숫자의 위치입니다.

참고: 등차수열 합 공식을 활용한 O(1) 풀이

정확히 하나의 숫자만 누락된 경우라면 등차수열의 합 공식을 이용해 반복문 없이도 답을 구할 수 있습니다. 전체 항 개수를 n이라 할 때 기대값은 (첫항 + 끝항) × n ÷ 2이며, 여기서 실제 배열 요소의 합을 빼면 누락된 숫자가 나옵니다.

const findMissingBySum = (arr = []) => {
    const n = arr.length + 1;
    const expected = ((arr[0] + arr[arr.length - 1]) * n) / 2;
    const actual = arr.reduce((sum, num) => sum + num, 0);
    return expected - actual;
};
console.log(findMissingBySum([7, 13, 19, 31, 37, 43])); // 25