findMissing.js

in about Dev on Algorithm

Codewars 알고리즘 풀이


Problem

  • An Arithmetic Progression is defined as one in which there is a constant difference between the consecutive terms of a given series of numbers.
    • Arithmetic Progression은 일련의 숫자의 연속적인 항에 일정한 차이가 있는 것으로 정의된다.
  • You are provided with consecutive elements of an Arithmetic Progression.
    • Arithmetic Progression의 연속적인 element가 주어진다.
  • There is however one hitch.
    • 하지만 하나의 장애가 있다.
  • Exactly one term from the original series is missing from the set of numbers which have been given to you.
    • 주어진 일련의 숫자들 중에서 정확히 하나가 빠져있다.
  • Find the missing term.
    • 누락된 항을 반환한다.
  • List size will always be at least 3 numbers.
    • 목록은 항상 3개 이상의 숫자이다.
  • The missing term will never be the first or last one.
    • 빠진 항은 첫 번째 또는 마지막이 될 수 없다.



Solution 01

function findMissing(arr) {
  const pattern = (arr[arr.length - 1] - arr[0]) / arr.length;
  
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] - arr[i - 1] !== pattern) {
      return arr[i - 1] + pattern;
    }
  }
  return null;
}

findMissing([1, 3, 4]);  // 2
findMissing([1, 2, 4]);  // 3


Solution 02

function findMissing(arr) {
  let expectedSum = ((arr[0] + arr[arr.length - 1]) * (arr.length + 1)) / 2;
  let sum = arr.reduce((total, i) => total + i);
  
  return expectedSum - sum;
}

findMissing([1, 3, 4]);  // 2
findMissing([1, 2, 4]);  // 3


Solution 03

function findMissing(arr) {
  let pattern = (arr[arr.length - 1] - arr[0]) / arr.length;
  let i = 0;
  
  while (arr[i] + pattern === arr[i + 1]) {
    i++;
  }
  return arr[i] + pattern;
}

findMissing([1, 3, 4]);  // 2
findMissing([1, 2, 4]);  // 3


Solution 04

function findMissing(arr) {
  let pattern = (arr[arr.length - 1] - arr[0]) / arr.length;
  
  return arr.filter((i, index) => i !== arr[0] + index * pattern)[0] - pattern;
}

findMissing([1, 3, 4]);  // 2
findMissing([1, 2, 4]);  // 3