 ## Recommended Posts  In this thread: anyone can share a programming problem and we will post solutions. The goal is to find solutions with impressive characteristics such as performance or brevity. This can be interpreted as recreational optimization or code golf.

Your first question (I will provide an example answer if there are no biters):

How would you locate gaps in a list of integers?

Example use case: determining which IDs have been deleted from a database

Example input: [1,3,4,5,8,9]

Example output: [2,6,7]

(Yes, this does not detect gaps at the tail of the list.)

##### Share on other sites  Here is a naive implementation: https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=ce526c0085e7ca3ddda57d6a753ffe16

This iterates over the array several times when it should only be required to iterate once. Feel free to use any language or introduce your own problems!

Edited by root
##### Share on other sites  ```function get_missing_ids(a) {
var res = []
var max = Math.max(...a);
for (i = 1; i < max; i++) {
var found = false
a.forEach(element => {
if (i == element) found = true
});
if (found == false) res.push(i)
}
return res
}

var a = [1, 3, 4, 5, 8, 9]
console.log(get_missing_ids(a))```
##### Share on other sites  ```\$ python3 updatedsec.py
1
10
7
5
4
Missing:
2
3
6
8
9```
```from sys import stdin
arr = []
for x in stdin:
arr.append(int(x))
arr = sorted(arr)
print("Missing:")
for i in range(len(arr)-1):
if arr[i+1] - 1 != arr[i]:
for x in range(arr[i]+1, arr[i+1]):
print(x)```

##### Share on other sites  Here is an implementation that uses (I think) two iterations, one to sort and then one for the gap detection. The gap detection algorithm should be O(n) rather than O(n^2) like my last implementation.

Edited by root