Finding the number in a list that differs in parity

Given any string with a series of numbers find out which one of the numbers differs from the others in evenness and return its position.

Examples:

• "2 4 6 7 8 10" returns 4

• "3 5 7 9 10" returns 5

I found 2 different ways to do so, but I'm wondering what is the best approach in matter of time complexity.

Solution 1

def num_test(numbers)
  (i = numbers.split.map(&:to_i)).index(i.partition(&:odd?).find(&:one?).first)+1
end

Solution 2

def num_test(numbers)
  numbers.index(numbers.split.map(&:to_i).partition(&:odd?).find(&:one?).first.to_s)+1
end

Also, any other solution is welcome.

Well, one way we can do it is by counting the first three elements. If more than one is odd, it means the sequence is odd, and we should look for an even number. If one or less is odd, the sequence is even, and we should look for an odd number.

a1 = "2 4 6 7 8 10"
a2 = "3 5 7 9 10"

def index_of_outlier(string)
  array = string.split(' ').map(&:to_i)
  count_of_odd = (array[0..2]).count { |i| i.odd? }
  if count_of_odd > 1
    array.index { |i| i.even? }
  else
    array.index { |i| i.odd? }
  end
end

puts index_of_outlier(a1) #=> 3 
puts index_of_outlier(a2) #=> 4

This looks messy, but it gets the job done quickly. The lower bound is \$3 + 1\$ iterations, and the upper bound is \$3 + n - 1\$. This makes it \$O(n)\$.

You need three iterations to determine the nature of the sequence and up to \$n - 1\$ more to find the solution.

I'm not sure how partition works under the hood, but I assume it traverses the array at least once. This means my solution will perform better if the target index is lower than \$n - 5\$.

If you want the char position in the string and not the array index, just add one to the result (as you are doing in your own solutions).

StackExchange Code Review Q#125332, answer score: 2