^^ or
This approach has the same time complexity as the obvious one
(comparing every element against the first) - it's O(N). In some
languages it might even have a smaller coefficient, because addition
can be cheaper than testing and branching on modern processors. No
Javascript interpreter is going to reduce the expression to
sufficiently low-level operations for that effect to appear, though.
(An APL compiler might, since this sort of thing is a common APL idiom.)
Then the summation method won't work - but the simple scan-and-compare
approach remains valid.
If we really want to overcomplicate things, here's an alternative that
works for three values: Treat the array as an N-digit trinary number.
(The code's a bit simpler if you treat it as little-endian, so
anarray[0] is the least-significant digit.) Convert that number to a
native integer, by multipling anarray[0] by 3, anarray[1] by 9, etc.
If the result is 0, you have an array of all zeros. If the result is
3**N - 1, you have an array of all twos (just as binary 1111 is 2**4 -
1). If the result is (3**N-1)/2, you have an array of all ones
(because eg trinary 1111 is trinary 2222 divided by 2). Any other
value, and you have a dark sheep.
The code for this can be written relatively elegantly. Unfortunately
it's pointless, since it's just more work for the same answer.
Obviously this can be extended to higher number bases, though
computing some of the allowed results is less convenient.
Why not?
You can use a data structure that gives you a constant-time solution
for this problem: an array that also tracks the minimum and maximum
values during insertion, any structure that gives you constant-time
access to the minimum and maximum values, etc. So a simple array does
not give you a time-optimal solution.
However, it seems unlikely a Javascript program will be asked to
perform this operation on an array so large that it makes any
discernible different.
First, use Array.min() and Array.max() to find the minimum and maximum
values in the array, then compare them.
Another O(N) solution, but now with a larger constant, since we're
probably looking at two passes through the array. (Array could find
both the minimum and maximum on the first pass and cache the values
for subsequent min() and max() calls; or it could track min and max
during insertion, using extra space to amortize those operations and
making this an O(1) solution. But I doubt any implementations do that.)
One more solution is interesting to me. Sort the array and then see if
the initial value is the same as the final value. It's a pretty
compact solution, but it could be slow if your array has a lot of
items in it. Without knowing the possibilities for your data, it's
hard to know what the best solution is.
Well, that's at best an O(N lg N) solution, so it's hard to see when
it ever wins.
But we can pessimize this further. Compute all rotations of the array
and see if their initial elements match: O(N**2). Do the same with all
permutations: O(N!).
But my favorite is to record the value of the first element, then
choose an element at random and see if they match. If not, return the
"dark sheep" result. If so, repeat with another random element.
Continue until you have reached a preset confidence level. (Computing
the probability of missing a dark sheep, given N elements, M trials, K
dark sheep, and an unbiased PRNG is left as an exercise for the reader.)
This probabilistic approach lets you decide just how much time you
want to waste over using the obvious approach, and how correct you
want to be. It maximizes flexibility, which we all know is always a
Good Thing.
