Home Posts Tags Post Search Tag Search

Post 35

Hacker Rank 09 - Fibonacci Numbers

Published on: 2025-06-06 Tags: elixir, Blog, Hacker Rank
So for this one we needed to find the Fibonacci numbers for a given set of indexes. So with the index starting at 0 with a value of 0, we need to find the value of each Fibonacci number given. The first number is the amount of indices that we need to find. Also they want the number mod 10^8 + 7, because why not...

Input
5
0
1
5
10
100

Output
0
1
5
55
24278230

The biggest thing that I wanted to do was to be able to keep all values of the Fibonacci in one list and then find the largest number so we only have to calculate it once then pull the indices. So for that I created this function.

    def first(n) when is_integer(n) and n >= 0 do # Helper function to start off the loop
        fib(n + 1, 0, 1 , [])
        # n + 1 as this assumes index 0 start and we want to be sure that we get the highest index in the list
        |> Enum.reverse() # This stores the numbers in reverse order so we need to reverse.
    end

    defp fib(0, _, _, acc), do: acc # When we get all the numbers we want just return the list
    defp fib(number, current, next, acc) do
        fib(number - 1, next, current + next, [current | acc]) 
    end

We have the base case at 0 because we are continuing to build numbers till we get to 0, this insures that we are only building the right amount of numbers. 

With the first number we send being 0 and the next being 1 we are building from 0 onward. So we start off by: 
reducing the number (number left in this case) by 1 
setting the next to current
setting the next to current + next
adding the current to the list

A very small bit of code to get what we need.

Okay so now we have a list of Fibonacci numbers in the right order and the right amount. Now we need to get the numbers we want from the list.

Well here is the great thing about how we made the list. 0 is index 0 so every number in the list should be at the index of the Fibonacci number it corresponds to. So if we have a list of indices that we want we need to find the fib for the largest of the list, then pop each value based off the index list we receive. 

    def find_fib(list) do
        max = find_max(list)
        map = first(max)
        
        Enum.map(list, fn index -> 
            {value, _map} = List.pop_at(map, index)
            value
        end)     
    end

As always I'll leave the IO.puts() part up to the reader.