Home > Software design >  missing integers from a sorted array
missing integers from a sorted array

Time:11-12

  • I have an array of sorted numbers being passed into my function
  • I want to return the number of numbers I'm missing

Example:

the array I pass is [1,5,6,9]

the numbers I'm missing are 2,3,4,7,8

the counter should be 5

what I'm attempting to do:

without using any built ins. while my next number in my list is not the next number already in my list I would increment by one.


function missing(numbers){
    counter = 0;
    let j = 1;
    for(let i = 0; i<numbers.length; i  ){
        while(numbers[i 1] != numbers[i] j){
            j =1;
            counter =1;
            console.log("missing "  numbers[i] j)
        }
    }
return counter;
}

CodePudding user response:

I'd suggest using a Set to contain all numbers in the input array, then generating a range array of all possible numbers corresponding to that array.

We do this by first getting the min and max of our input array, then generating the range from min to max.

Then we use Array.filter() to remove all items in the range array in our original array (in the Set)

function getMissingNumbers(arr) {
    const [min,max] = [Math.min(...arr), Math.max(...arr)];
    const range = Array.from({ length: (max - min   1)}, (v,k) => k   min);
    const nSet = new Set(arr);
    return range.filter(n => !nSet.has(n));
}

console.log(getMissingNumbers([1,5,6,9]))
console.log(getMissingNumbers([1,5]))
console.log(getMissingNumbers([2,3,4,5,8,9]))
.as-console-wrapper { max-height: 100% !important; top: 0; }
<iframe name="sif1" sandbox="allow-forms allow-modals allow-scripts" frameborder="0"></iframe>

And a slightly simpler version (assuming arrays are sorted):

function getMissingNumbers(arr) {
    let s = new Set(arr);
    let range = Array.from({ length: (arr[arr.length-1] - arr[0])}, (v,k) => k   arr[0]);
    return range.filter(n => !s.has(n));
}

console.log(getMissingNumbers([1,5,6,9]))
console.log(getMissingNumbers([1,5]))
console.log(getMissingNumbers([2,3,4,5,8,9]))
.as-console-wrapper { max-height: 100% !important; top: 0; }
<iframe name="sif2" sandbox="allow-forms allow-modals allow-scripts" frameborder="0"></iframe>

CodePudding user response:

You could take a single loop and run from index zero to the end of the given array.

At the same time use an variable for the increasing value and if not in the array push this value to the result set of missing values.

function getMissing(array) {
    let i = 0,
        v = array[0],
        result = [];
    
    while (i < array.length) {
        if (v === array[i]) {
            i  ;
            v  ;
            continue;
        }
        result.push(v  );
    }
    return result;
}


console.log(...getMissing([1, 5, 6, 9])); // 2 3 4 7 8
<iframe name="sif3" sandbox="allow-forms allow-modals allow-scripts" frameborder="0"></iframe>

CodePudding user response:

function missing(numbers){
    counter = 0;
  
    for(let i = 0; i<numbers.length; i  ){
        let j = 1;
        while(numbers[i 1] != numbers[i] j && numbers[i] j < 10){
            console.log(`missing   ${numbers[i] j}`, numbers[i], j)
            j =1;
            counter =1;
        }
    }
    return counter;
}

There are some issues with your logic.

  1. First, you're expecting missing numbers till 9, which is missing from your while condition.
  2. You're not resetting the j variable once you're out of the while loop.
  3. You're incrementing j before the print statement giving you wrong values which could've failed the while condition.

CodePudding user response:

You can also try using 2 loops inside one another

function missingNumbers(arr) {
      const arr2 = [];
      for (let i = arr[0]; i <= arr[arr.length - 1]; i  ) {
        arr2.push(i);
      }
      if (arr.length === arr2.length) {
        return [];
      }
      for (let i = 0; i < arr2.length; i  ) {
        for (let j = 0; j < arr.length; j  ) {
          if (arr2[i] === arr[j]) {
            arr2.splice(i, 1);
          }
        }
      }
      return arr2;
    }
    
    console.log(missingNumbers([1,5,6,9]))
    console.log(missingNumbers([1,5]))
    console.log(missingNumbers([2,3,4,5,8,9]))
    console.log(missingNumbers([1,2]))
<iframe name="sif4" sandbox="allow-forms allow-modals allow-scripts" frameborder="0"></iframe>

  • Related