[Leet Code Top 100] #268. Missing Number

문제 정보

• Leet Code 문제 링크
• 난이도 : Easy

 

해결 방법

문제 자체는 쉬운 편이어서 곧바로 Follow up 의 조건을 포함해서 구현하려고 했습니다. 이런 저런 알고리즘을 생각하다 보니 어느 순간 '다 더해서 빼면 되겠다' 라는 생각이 들었습니다.

Follow up:
 Could you implement a solution using only O(1) extra space complexity and O(n) runtime complexity?

Discuss 탭을 보던 중 한줄만에 구현한 댓글도 있었습니다. 컨셉은 동일하나 reduce 를 자주 사용하진 않아 문제를 고민할 때는 미처 생각이 나지 않는 것 같습니다.

return -nums.reduce((acc,num,i)=> acc+num-i-1,0);

 

소스 코드

// Leet Code
// #268. Missing Number
// Success
// Runtime: 84 ms, faster than 70.62% of JavaScript online submissions for Missing Number.
// Memory Usage: 41.3 MB, less than 47.42% of JavaScript online submissions for Missing Number.

function main(){
    // Input // Output
    nums = [9,6,4,2,3,5,7,0,1]; // 8

    console.log(missingNumber(nums));
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var missingNumber = function(nums) {
    const n = nums.length;
    let sum = (1 + n) * n / 2;
    for(let idx = 0; idx < n; idx++){
        sum -= nums[idx];
    }
    return sum;
};

main();

 

참고 자료

• LeetCode Top 100 Problem Selection
• LeetCode - [Javascript] Simple solution, faster than 99.08% submissions