Swift-function for finding missing Integers in an array of sequential Integers

Question

Task description:

Implement a function, which receives an array of unsorted numbers from 1 to 100. In the array zero or more numbers might be missing. The function shall return an array containing the missing numbers.

Provided Test-data with expected result:

var arrTest = Array(1...100)
arrTest.remove(at: 25)
arrTest.remove(at: 20)
arrTest.remove(at: 6)
print(findMissingIn(numbers: arrTest))

With these test-data your function shall return [7, 21, 26] as missing numbers.

My solution:

func findMissingIn(numbers: [Int]) -> [Int] {
 var missingNums = [Int]()
 
 for i in 1...100 {
 if numbers.contains(i) == false {
 missingNums.append(i)
 }
 }
 
 return missingNums
}

My function returns the expected result. So I guess it's formally correct.

- Is there a better solution?

- What's your opinion about my naming and coding-style in general. Would you have done it differently. How? Why?

Answer 1

In the spirit of the Swift API Design Guidelines, in particular

Prefer method and function names that make use sites form grammatical English phrases.

I would call the method

func missingNumbers(in numbers: [Int]) -> [Int]

so that it is used as

print(missingNumbers(in: arrTest))

Comparing a boolean value with true or false is unnecessary, i.e.

if numbers.contains(i) == false { ... }

is (in my opinion) better written as

if !numbers.contains(i) { ... }

Instead of an explicit loop and a temporary array we can apply filter to a range:

func missingNumbers(in numbers: [Int]) -> [Int] {
 return (1...100).filter { !numbers.contains(0ドル) }
}

which is concise but still easy to read.

(The return keyword can be omitted if the function body consists of a single expression, that is a matter of personal taste.)

If many containment test are done against the same collection of values then it can be advantageous to convert the array to a Swift Set first because Set.contains() is a \$ O(1) \$ operation. It probably makes no performance difference for 100 values, but this is what it would look like:

func missingNumbers(in numbers: [Int]) -> [Int] {
 let set = Set(numbers)
 return (1...100).filter { !set.contains(0ドル) }
}

• ielyamani: Searching for elements in a Set is indeed O(1) but the hashing adds a constant that may not be negligible in some situations twitter.com/iklilelyamani/status/1077298360632135680 . The Strategy Pattern could be used to choose the appropriate data structure based on the count of elements in numbers
• Martin R: @ielyamani: Can you share your benchmarking code?
• ielyamani: Back then, I used Attabench
• ielyamani: For example, this minimalistic solution gives me a 20X better time on my local machine. Optimizations can be turned on with -O in the settings of SwiftFiddle.