dines - 8 months ago 30

Ruby Question

I'm doing Katas at codewars and I on occasion pass all the tests but fail due to timeout reasons. Could you please help with comments on how to improve my code by refactoring the code below.

`arrA`

`arrB`

`rng`

`wanted`

`def find_arr(arrA, arrB, rng, wanted)`

common = arrA && arrB

range = (rng[0]..rng[1]).to_a.select {|num| common.include?(num)}

range_wanted = range.select {|num| wanted == "odd" ? num.odd? : num.even?}

numbers_twice = range_wanted.select {|num| arrA.count(num) > 1 && arrB.count(num) > 1}

end

Answer

There is a lot of issues here, mainly time complexity is O(n^2) because of the last line which counts number occurrences in both arrays. For each number in `range_wanted`

it needs to iterate over all elements of both arrays. This is highly inefficient.

Try to run your code in irb with those arguments `find_arr([], [], [1, 10_000_000], "odd")`

or bigger range.

Here are some suggestions how to improve this code:

- Count occurrences yourself by storing them in a hash
- When counting you can skip those numbers that don't meet requirements, range and odd/even
- If you want to check if value is in a range, you should use
`cover?`

method from`Range`

class. Do not change range into array and iterate over it. - In this line
`range_wanted = range.select {|num| wanted == "odd" ? num.odd? : num.even?}`

you are testing`wanted == "odd"`

in every iteration, but this won't ever change as it is passed as argument. You can move this condition outside of loop

Here is refactored code. I wrote it out of my head, so there may be some issues but it should give you an idea on how to write your own solution.

```
def find_arr(arrA, arrB, rng, wanted)
countA = Hash.new(0)
countB = Hash.new(0)
# If wanted == "odd" we want to test elem % 2 == 1, otherwise elem % 2 == 0
remainder = wanted == "odd" ? 1 : 0
range = (rng[0]..rng[1])
arrA.each do |elem|
if range.cover?(elem) && (elem % 2 == remainder)
countA[elem] += 1
end
end
arrB.each do |elem|
if range.cover?(elem) && (elem % 2 == remainder)
countB[elem] += 1
end
end
result = []
countA.each do |elem, count|
if count > 1 && countB[elem] > 1
result.push(elem)
end
end
result
end
```

Source (Stackoverflow)