Hey guys! In this article, I will be detailing the steps to solve HackerRank's Even Fibonacci number algorithmic problem. I'll be doing this in Ruby, but the process should work for any other programming language. Like many people, you probably already tried to tackle this but your solution failed some test cases due to a timeout error (we'll talk more about this in a bit). Let's dive in.

What is a Fibonacci sequence?

To simply put it, a Fibonacci is a number sequence where each number is the sum of the previous two numbers. For instance, if you have the following number sequence: 1, 2, 3, 5, 8, 13, you'll see that 3 is the sum of 1 and 2, while5 is the sum of 2 and 3. That logic continues for every number in the sequence until 13.

HackerRank's Problem

The first step is understanding the problem.

If you already understand the question, you can skip to the solution section of this article.

The program takes in two inputs, T which represents the number of test cases that your code must pass and N which represents the Integer in each test case. That said, we are expected to find the sum of all even numbers in a Fibonacci sequence up until N. For instance if N is 35, the Fibonacci sequence will be 1, 2, 3, 5, 8, 13, 21, 34, then we will extract all the even numbers in that sequence and sum them up like so, 2 + 8 + 34 = 44.

This program has an execution limit of 10s, which means it is not enough for our logic to be correct, but we must also optimize our code to execute under 10s for every test case provided by Hacker Rank, else our code will fail some tests due to a timeout error. If you want, you can read more on Hacker Rank's timeouts/execution limit here

Solution

As shown in the image above, HackerRank already has a code snippet that is collecting the input (T and N), so we won't be providing any data. We just need to write an algorithm that will work for any integer.

The first thing we'll do is initialize two variables for our starting points, we'll call them previous and current, and we'll give them values 1 and 2 respectively. These are the two variables we will keep summing up and changing their values until our sequence reaches N.

Next, we need a while loop that keeps running as long as the current number is less than the value of N.

On every iteration of our while loop, we need to assign the value of current to previous and assign the sum of previous + current to current i.e: since the initial values of previous and current are 1 and 2, on the first iteration, previous = current and current = previous + current. This means previous is now 2 and current is now 3. To achieve this easily, we will use Ruby's parallel assignment, as it allows us to assign values to multiple variables at the same time. You can read more on parallel assignments here.

The above code gives us the Fibonacci sequence for N, but we need to now get all even number in the sequence and print out their sum. Let's do that!

To get the even number, we need to check if the value of current is an even number and keep summing it up on every iteration where that condition is met. To achieve this, we need a variable outside the loop where we'll compute the sum of the even numbers, so we'll call it sum_of_even and give it an initial value of zero. Now, whenever current is an even number, we'll add it to our sum_of_even variable. When the loop completes, we'll print out the value of sum_of_even.

t = gets.strip.to_i
for a0 in (0..t-1)
    n = gets.strip.to_i

    previous = 1
    current = 2
    sum_of_even = 0

    while current < n
      sum_of_even += current if current.even?
      previous, current = current, previous + current
    end

    puts sum_of_even
end

Notice that we're computing our sum_of_even before changing the values of previous and current.

Now, if we submit our code, it passes all test cases!

That's it! If you have a contribution or correction, please leave a note in the comment section.