First, a bit of background:
I'm working on one of the Codility lessons, and, even though this is easy to solve, logistically, it is less than easy to solve, performance-wise.
I've been able to boil it down to just this:
public func solution(_ A : inout [Int]) -> Int {
let B = A // Assigning it to a local speeds it up.
return Array<Int>(Set(B)).sorted(by: {$0<$1}).reduce(0) { ($1 == $0 + 1) ? $1 : $0 } + 1
}
However, this is just a WEE bit too slow. I guess that the main reason is that the reduce goes through ALL elements of an array, even though the answer may be early. I may not be able to speed it up.
But I'd like to try. The part that I'm looking at is this:
.reduce(0) { ($1 == $0 + 1) ? $1 : $0 }
I'm wondering if I can make that comparison more efficient.
I have to check if $1 is equal to $0 + 1. I can't avoid that comparison.
The ternary operator is not actually faster than an if clause, but it looks cooler ;).
Is there a higher-performance way to compare two positive integers for equivalence than the basic "==" operator?
BTW: This is not a "do my homework for me" question. It's pretty legit, and these Codility lessons don't give you credit or anything. They are just a fun exercise. I want to know how to do this, as I'm sure I'll need it in the future.
Using the solution suggested by @TNguyen in comments, below piece of code got 100% on both correctness and performance.
You just need to generate the correct Array, containing each Integer in the range [1..(N + 1)] by calling Array(1...A.count+1). Then you sum its elements using reduce(0,+) and finally substract the sum of the elements of the input array A. The difference between the two sums gives the missing element.
public func solution(_ A : inout [Int]) -> Int {
return Array(1...A.count+1).reduce(0,+)-A.reduce(0,+)
}
An even faster solution is to use the mathematical formula1+2+...+n=n(n-1)/2 for the first sum.
public func solution(_ A : inout [Int]) -> Int {
return (A.count+1)*(A.count+2)/2-A.reduce(0,+)
}