Select the element out of the array if its index is a Fibonacci number [closed]

Question

I've some questions for an exam and wondered if somebody could take a look at my Fibonacci sequence that is supposed to answer this question:

"select the element out of the array if its index is a Fibonacci number"

---

def fibonacci_sequence(max_num)
  sequence = [1, 2]
  loop do
    fibonacci = sequence[-2] + sequence[-1]
    break if fibonacci >= max_num
    sequence << fibonacci
  end
  sequence
end

# array size
max_num = 100
numbers = []
1.upto(max_num) { |num| numbers << num }
fibonacci = fibonacci_sequence(max_num)

# select fibonacci numbers and assign array to variable
fibonacci_numbers = numbers.select { |num| fibonacci.include?(num) }

My thoughts were that I had to work out what the Fibonacci sequence was before I could select numbers out of the array that were Fibonacci. The thing is I already answer the question by assigning these numbers to the Fibonacci variable. I've then used a select method on the original numbers array even though I already know what the output is going to be.

Have I gone about this the right way? I'm thinking no!

Answer 1

Some notes:

• fibonacci_numbers = numbers.select { |num| fibonacci.include?(num) }. Array#include? is O(n), this will be very slow. With this approach, fibonacci should be a set.

• Since you have to store a the fibonacci values, the space complexity won't be nice for big inputs.

• Your algorithm only works for arrays, it would be nice if it worked with enumerables.

I'd write:

def remove_fib_indexes(xs)
  Enumerator.new do |yielder|
    fib_a, fib_b = [0, 1]
    xs.each.with_index do |x, idx|
      if idx == fib_a
        # skip the repeated 1 in the sequence [0, 1, 1, 2, 3, 5, ...]
        fib_a, fib_b = (fib_b == 1) ? [1, 2] : [fib_b, fib_a + fib_b] 
      else
        yielder.yield(x)
      end
    end
  end
end

xs = (0..Float::INFINITY).lazy.map(&:to_s)    
remove_fib_indexes(xs).take(10).to_a
#=> ["4", "6", "7", "9", "10", "11", "12", "14", "15", "16"]