Find the odd int - Ruby Nested Loop Error

Question

I was doing this question on codewars: "Given an array, find the int that appears an odd number of times. There will always be only one integer that appears an odd number of times."

Code:

def find_it(seq)
  int = []
  for a in seq do
    count = 0
    for b in seq do
      if a == b
        count += 1
      end
    end
    if count % 2.0 != 0
      int << b
    end
  end      
  puts int.uniq[0].to_i
end

It was tested against a couple inputs, but the answers were wrong for these two arrays:

find_it([1,1,2,-2,5,2,4,4,-1,-2,5]) - returns 5 instead of -1

find_it([1,1,1,1,1,1,10,1,1,1,1]) - returns 1 instead of 10

What went wrong with my code?

Answer 1

if count % 2.0 != 0
      int << b
    end

The problem you have here is that your pushing b instead of a into the integer array, so what's happening is that instead of the value that you counted being pushed in, your pushing in the last value of b which is the last value element in the array regardless as long as the condition that the counter is an odd number, although b and counter have nothing to do with each other. so to fix it you replace b with a so that it pushes in the value you are testing comparing with the other elements in the second loop

fix:

if count % 2.0 != 0
      int << a
    end

a similar yet simpler code that does a similar job except in a shorter and more understandable way is:

def find_it(seq)
  numberWithOddCount = 0
  seq.each do |currentElement|
    counter = 0
    seq.each { |elementToCompare| counter += 1 if currentElement == elementToCompare}
    numberWithOddCount = currentElement if counter % 2 != 0
  end
  numberWithOddCount
end

Just added a few tid-bits that you could also utilize to shorten and simplify code.

Happy Coding!

Note:

You could utilize built in ruby methods in creative ways to make the code do what you want in very few lines (or even one line) such as what @iGian did in the questions comments, but if your still new to ruby then its best to utilize those methods one by one when learning them otherwise you'll be confused. But if your willing to take the time now to learn them, I suggest you take his code and separate each method execution into its own line and output what each method had done to know what's doing what. and practice using each separately.

Answer 2

@aimen_alt is right about your mistake

but let's decompose your problem.

First, you need to calculate the appearances of each number. Second, you need to find the one with the odd count of the appearances. Accordingly to the problem, there is only one such number, so you can return it right away.

You can go your way and do it in O(N^2) complexity by scanning your sequence for each item in the sequence (so N items in the sequence multiply by the size of the sequence N = N*N). You can do it linearly* by constructing a Hash and than you'll be able to get the key with odd value:

def find_it(seq)
  numbers = {}
  seq.each do |item|
    numbers[item] = numbers[item].to_i + 1
  end
  numbers.select{ |k,v| v.odd? }.first.first
end

to be more idiomatic you can use group_by to group the numbers themselves:

seq = [1, 2, 6, 1, 2]
seq.group_by{ |item| item }
#=> {1=>[1, 1], 2=>[2, 2], 6=>[6]}

You can see that each value is an Array, and you just need to get one with the odd amount of items:

seq = [1, 2, 6, 1, 2]
seq.group_by{ |item| item }.select{ |k, v| v.size.odd? }
#=> {6=>[6]}

And the last thing you would like to do is to get the value of the key:

seq.group_by{ |item| item }.select{ |k, v| v.size.odd? }.keys.first

So, the final solution would be

def find_it(seq)
  seq.group_by{ |item| item }
     .select{ |k, v| v.size.odd? }
     .keys
     .first
end

as @pascalbetz mentioned:

def find_it(seq)
  seq.group_by{ |item| item }
     .find{ |k, v| v.size.odd? }
     .first
end