javascript - Find a missing number in a sequence using .reduce - Stack Overflow

admin管理员组

文章数量:1357398

var o = [1,2,3,5,6,7,8]

var res = o.reduce(function(x,y){

   return !((y-x)===1)?y-1:'Nothing'

})
console.log(res)//7

Output should be 4, want to know if it is possible using reduce or functionally (Not through loops)? it only works if the missing value is before the last value of an array.

var o = [1,2,3,5,6,7,8]

var res = o.reduce(function(x,y){

   return !((y-x)===1)?y-1:'Nothing'

})
console.log(res)//7

Output should be 4, want to know if it is possible using reduce or functionally (Not through loops)? it only works if the missing value is before the last value of an array.

• javascript

Share Improve this question Follow edited Mar 19, 2017 at 14:46 georg 215k5656 gold badges322322 silver badges400400 bronze badges asked Mar 19, 2017 at 14:42 Sean TSean T 5111 gold badge22 silver badges77 bronze badges 5

• 1 why output should be 4? – Satpal Commented Mar 19, 2017 at 14:44
• Because that is the missing number in this array, if you iterate it by one till 8 – Sean T Commented Mar 19, 2017 at 14:45
• 1 reduce goes through all elements; it doesn’t stop. If you return "Nothing", eventually the subtraction is going to be "Nothing" - x, where x is a number. Try it with find instead. – Sebastian Simon Commented Mar 19, 2017 at 14:47
• 1 “It only works if the missing value is before the last value of an array.” — That’s like saying that a broken clock shows the correct time only twice a day. – Sebastian Simon Commented Mar 19, 2017 at 14:49
• @Xufox I used reduce because i thought to get a single value from an array it is useful, i didn't try find i have to check. – Sean T Commented Mar 19, 2017 at 14:52

Add a ment  | 

6 Answers 6

Sorted by: Reset to default 3

You can use reduce to pute the actual sum of all elements and then subtract it from the target sum (n(a0+an)/2). This gives you the missing number.

var o = [1,2,3,5,6,7,8];

var len = o.length;
var sum = (len + 1) * (o[0] + o[len - 1]) / 2;
var res = sum  - o.reduce((x,y) => x + y);

console.log(res);

Note that this works with any starting value and any step, e.g. for [3,5,7,11] it will correctly print 9. The only requirement is that o should be an arithmetic progression.

You could use a start value and check the previous element and the actual element.

var o = [1, 2, 3, 5, 6, 7, 8],
    res = o.reduce(function(r, a, i, aa) {
        return !i || r !== undefined || aa[i - 1] + 1 === a ? r : aa[i - 1] + 1;
    }, undefined);

console.log(res);

Instead of reduce you could use find, which will not look any further once it finds a missing value:

const o = [1,2,3,5,6,7,8];
const res = o.find( (x,i) => o[i+1]-x > 1 ) + 1;
console.log(res)//4

It's always good to generalize these jobs. So you should provide a series descriptor function for the algorithm to find which item is missing in the series. Let's do it;

function findMissingItem(a,s){
  return s(a[a.findIndex((f,i,a) => i ? f !== s(a[i-1]) : false)-1]);
}
var data1 = [1,2,3,5,6,7,8],
    data2 = [1,4,9,16,36,49,64,81],
  series1 = n => n+1,
  series2 = n => Math.pow(Math.sqrt(n)+1,2);
     res1 = findMissingItem(data1,series1),
     res2 = findMissingItem(data2,series2);
console.log(res1);
console.log(res2);

Here's a simple solution using Array.reduce and the ES6 arrow function for brevity.

const array = [1, 2, 3, 5, 6, 7, 8];
const result = array.reduce((result, x) => x > result ? result : x + 1, 1)
console.log(result); // 4

---

With a little refactoring, we can start to make the solution more generic.

const sequence = [1, 2, 3, 5, 6, 7, 8];
const result = sequence.reduce(missingLinkReducer, sequence[0])

function missingLinkReducer(expected, actual) {
  return expected === actual ? nextValue(expected) : expected;
}

function nextValue(value) {
  return value + 1;
}

console.log(result);

---

Going a little bit further, we can make it so that different functions can be plugged in for calculating the next value.

const sequence = [1, 2, 3, 5, 6, 7, 8];
const result = sequence.reduce(createMissingLinkReducer(increment), sequence[0]);
console.log(result + ' is missing from ' + sequence);


const sequenceB = [1, 2, 4, 8, 16, 64, 128];
const resultB = sequenceB.reduce(createMissingLinkReducer(double), sequenceB[0]);
console.log(resultB + ' is missing from ' + sequenceB);


function createMissingLinkReducer(nextValue) {
  return function missingLinkReducer(expected, actual) {
    return expected === actual ? nextValue(expected) : expected;
  }
}

function increment(value) {
  return value + 1;
}

function double(value) {
  return value * 2;
}

You can use every for this, below will work for any sequence interval you specify - it will return -1 if all elements are in sequence, or the element that doesn't fit:

var o = [1, 4, 7, 10, 11]
var seqInterval = 3;

function getMissing(arr, interval) {
  var hit = -1;
  var res = arr.every(function(e, i) {
    hit = i === 0 ? hit : ((e - interval) === arr[i - 1] ? -1 : e);
    return hit === -1;
  });
  return hit;
}

console.log(getMissing(o, seqInterval));

var o1 = [1,2,3,5,6,7,8];
var seqInterval1 = 1;
console.log(getMissing(o1, seqInterval1));

本文标签： javascriptFind a missing number in a sequence using reduceStack Overflow