Find the missing term in an Arithmetic Progression

发表于 | 分类于

题目描述

An Arithmetic Progression is defined as one in which there is a constant difference between the consecutive terms of a given series of numbers. You are provided with consecutive elements of an Arithmetic Progression. 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. The rest of the given series is the same as the original AP. Find the missing term.
You have to write the function findMissing(list), list will always be at least 3 numbers. The missing term will never be the first or last one.

Example :
findMissing([1,3,5,9,11]) == 7

PS: This is a sample question of the facebook engineer challenge on interviewstreet. I found it quite fun to solve on paper using math, derive the algo that way.

我的代码

var findMissing = function (list) { 
  var len = list.length;
  var x = Math.abs((list[1]-list[0])) < Math.abs((list[len-1]-list[len-2])) ? Math.abs((list[1]-list[0])):Math.abs((list[len-1]-list[len-2]));
  console.log(x);
  for(i=0; i<len; i++){
    if(list[len-1] > list[0]){
      if(list.indexOf(list[i]+x) == -1)
      return list[i]+x;
    }else if(list[len-1] < list[0]){
      if(list.indexOf(list[i]-x) == -1)
      return list[i]-x;
    }
  }
}

Clever

var findMissing = function (list) { 
    var step = (list[list.length - 1] - list[0]) / (list.length); 
    return list.filter(function(val, index) { return val !== (list[0] + index * step); })[0] - step; 
}

Key

  • 关键点1要找到等差值，利用题目中给的信息：第一个和最后一个数不会缺失；将这两个数分别与它们的后一个和前一个数相减，小的那个差就是等差值；

  • 关键点2要注意数列中可能有负数，按照关键点1求等差值的做法，则求解的时候要取绝对值；且需要判断数列是递增还是递减；

-------------完-------------