How to Check Any Missing Number from a Series of Numbers

How to check any missing number from a series of numbers?

A solution without hardcoding the 9:

select min_a - 1 + level
     from ( select min(a) min_a
                 , max(a) max_a
              from test1
          )
  connect by level <= max_a - min_a + 1
    minus
   select a
     from test1

---

Results:

MIN_A-1+LEVEL
-------------
         7003
         7007
         7008
         7009

4 rows selected.

How to find missing numbers in a sequence?

sequence <- c(12:17,1:4,6:10,19)

seq2 <- min(sequence):max(sequence)

seq2[!seq2 %in% sequence]

...and the output:

> seq2[!seq2 %in% sequence]
[1]  5 11 18
> 

Given a sequence of numbers how to identify the missing numbers

The shortest solution in Postgres is with standard SQL EXCEPT:

WITH tbl(x) AS (SELECT unnest ('{1,2,3,4,5,6,8,10,11}'::int[]))
-- the CTE provides a temp table - might be an actual table instead
SELECT generate_series(min(x), max(x)) FROM tbl
EXCEPT ALL
TABLE  tbl;

The set-returning function unnest() is Postgres specific and just the shortest syntax to provide your set of numbers as table.

Also works with duplicates or NULL values in the data.

TABLE tbl is (standard SQL!) short syntax for SELECT * FROM tbl:

• Is there a shortcut for SELECT * FROM in psql?

Related (with more explanation):

• Select rows which are not present in other table
• How to check a sequence efficiently for used and unused values in PostgreSQL

What's the best algorithm to find a missing number between two sorted numbers?

Here is a solution in C++ 17,

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    vector<int> v1 {1, 2, 3, 6, 7, 9, 15};

    auto const it = std::adjacent_find(v1.begin(), v1.end(),
                    [] (auto const a, auto const b) {
                    return b - a == 2;
                    } );

    if (it == v1.end()) {
            std::cout << "no matching\n";
    } else {
            std::cout << "the missing number: " << 1 + *it << '\n';
    }
}

Finding missing number in unordered arithmetic progression takes too long

As the code challenge guarantees that the minimum and maximum are present in the input, you can derive the step from the following info:

• minimum
• maximum
• length

Given the minimum and the step, you can easily go through the sequence of expected values and verify they are in the set of input values.

Here is an implementation:

function find(seq) {
    let low = seq[0];
    let high = low;
    for (let i of seq) {
         if (i < low) low = i;
         else if (i > high) high = i;
    }
    let step = (high - low) / seq.length;
    let set = new Set(seq);
    for (let i = low + step; i < high; i += step) {
        if (!set.has(i)) return i;
    }
}

NB: I didn't use Math.min(...seq) here, as for very large arrays that will run into stack size limitations.

Alternative solution

As discussed in comments, we could calculate what the expected sum would be if there were no missing number in the sequence (based on the minimum and maximum in the input, and its length) and subtract the actual sum from that: the difference would be the missing number.

As this sum could be large and even overrun the maximum safe integer for the number data type in JavaScript, we should then shift the input numbers to a "safe" area (around 0) so that the sum will be close to zero. This way we avoid the inaccuracies that would be introduced if the sum would move out of the safe-integer range.

Here is how that looks:

function find(seq) {
    let low = seq[0];
    let high = low;
    for (let i of seq) {
         if (i < low) low = i;
         else if (i > high) high = i;
    }
    let step = (high - low) / seq.length;
    let mid = low + Math.floor((high - low) / 2);
    let expectedSum = (low - mid + high - mid) * (seq.length + 1) / 2;  
    let sum = 0;
    for (let i of seq) {
        sum += i - mid;
    }
    return expectedSum - sum + mid;
}

---

Related Topics