Best way to find a number in an array that's "out of order"?

Question

I have an array of length 10 filled with numbers 0-9.

The numbers are (for the most part) in sequential order. However the number at the starting index can be any number, and whether the numbers are in ascending or descending order is unknown (the numbers wrap around once they hit the min/max number - 0 once it reaches 9, and vice-versa).

Exactly one of these numbers are not in order (as if it's been plucked out and randomly inserted back into the array).

Example:

[4, 3, 1, 0, 9, 8, 7, 2, 6, 5]

The number 2 at index 7 is out of order. The "gap" in numbers between indexes 1 and 2 is okay, and neither the number 3 or 1 is considered out of order.

What's the best way to pinpoint the index of the out-of-order number?

More examples - out of place numbers are marked with *:

[2, 3, *0, 4, 5, 6, 7, 8, 9, 1]
[5, 6, 7, 9, *8, 0, 1, 2, 3, 4]
[7, 6, 5, 4, 3, *8, 2, 1, 0, 9]
[0, *5, 1, 2, 3, 4, 6, 7, 8, 9]
[4, 3, *0, 2, 1, 9, 8, 7, 6, 5] 

Answer 1

To find the number that is out-of-order you have look at every element in the array. So, you have to iterate over the entire array with complexity O(n).

When you loop through the array, you should

• calculate the absolute value of the difference between the previous number and the current number.
• calculate the absolute value of the difference between the current number and next number

If both the above differences are greater than 1 and not equal to n-1 (when the difference is n-1, that is the point where your array flips), then that is number that is out of order.

Answer 2

Look at every other element, and compute the differences.

If most differences are positive, the order is ascending. If most are negative, it's descending; it can be decided exactly like the other case and i will not examine it further.

Of course you need to wrap around and compute the diff between (N-1)th and 0th element, or whatever.

From now on look at the diffs modulo N.

If the diff is 2, this is the regular case of no extra or missing elements; ignore it.

If the diff is 3, an element was yanked from somewhere around here. But we are not looking for its old place, we are looking for its new place; ignore this too.

If the diff is 1, then the out of order element is between these numbers.

If you have any other diff, then you must have two of them next to each other. The out of order element is the one that produces both of these diffs.

In the case of two consecutive numbers swapped, either one can be considered out of order. The diffs produced will be either (1,3) or (3,1) next to each other. This method picks one of the two possible answers.

For the arrays in question:

array -> 2 3 0 4 5 6 7 8 9 1(2)        
          \ / \ / \ / \ / \ /
diffs ->  -2   5   2   2   -7(=3 mod 10)
             *

In further examples I will not state equality mod 10 to save space.

array -> 5 6 7 9 8 0 1 2 3 4(5) 
          \ / \ / \ / \ / \ /
diffs ->   2   1   3   2   2
               *

array -> 7 6 5 4 3 8 2 1 0 9(7)        
          \ / \ / \ / \ / \ /
diffs ->  -2  -2  -1  -2  -3
                   *

array -> 0 5 1 2 3 4 6 7 8 9(0)        
          \ / \ / \ / \ / \ /
diffs ->   1   2   3   2   2
           *

array -> 4 3 0 2 1 9 8 7 6 5(4)       
          \ / \ / \ / \ / \ /
diffs ->  -4  -9  -3  -2  -2
             *    

More examples:

array -> 0 2 1 3 4 5 6 7 8 9(0)        swapped adjacent elements, case 1
          \ / \ / \ / \ / \ /
diffs ->   1   3   2   2   2
           *

array -> 0 1 3 2 4 5 6 7 8 9(0)        swapped adjacent elements, case 2
          \ / \ / \ / \ / \ /
diffs ->   3   1   2   2   2
               *

array -> 0 2 3 4 5 6 7 1 8 9(0)        element removed and inserted at odd pos
          \ / \ / \ / \ / \ /
diffs ->   3   2   2   1   2
                       *

array -> 0 2 3 4 5 6 1 7 8 9(0)        element removed and inserted at even pos
          \ / \ / \ / \ / \ /
diffs ->   3   2   6   7   2
                     *

array -> 0 7 1 2 3 4 5 6 8 9(0)        element removed and inserted at odd pos
          \ / \ / \ / \ / \ /
diffs ->   1   2   2   3   2
           *            

array -> 0 1 7 2 3 4 5 6 8 9(0)        element removed and inserted at even pos
          \ / \ / \ / \ / \ /
diffs ->   7   6   2   3   2
             *

Answer 3

The following contrived examples do not have a unique solution. You need to decide what happens in these cases:

0, 1, 2, 3, 4, 5, 6, 7, 8, 9 // first item move to end

2, 1, 3, 4, 5, 6, 7, 8, 9, 0 // adjacent items swapped 

For all other cases, luckily the telling trait is that the "out-of-order" item will be more than 1 away from both its neighbors (because #2 above).

for (i = 0; i < arr.length; i++) {
    int priorIndex = (i-1) % arr.length;
    int nextIndex = (i+1) % arr.length;
    int diffToPriorValue = abs(arr[i] - arr[priorIndex]);
    int diffToNextValue = abs(arr[i] - arr[nextIndex]);
    if (diffToPriorValue > arr.length/2)
        diffToPriorValue = arr.length - diffToPriorValue; // wrap-around
    if (diffToNextValue > arr.length/2)
        diffToNextValue = arr.length - diffToNextValue; // wrap-around
    if (diffToPriorValue != 1 && diffToNextValue != 1)
        return i;
return -1;