Practice Algorithms with Math Puzzles Part 2
Hello, I will explain two algorithms to find the kth even and the kth odd numbers in the Fibonacci series.
If you haven’t heard of it, Fibonacci series is this:
The even items of it are 2, 8, 34 and so on. The first way that comes to mind is to generate the series using a for loop and keep track of even numbers as we go ahead and as soon as we get to the kth even number we exit and return it.
But if you pay attention to the even numbers of Fibonacci series and play a little with them, you will notice there is a formula to generate them:
This way we do not need all the previous numbers of Fibonacci series up to that point when we want to find the nth even number. The following function follows image 2 and returns what we want.
In line 3 ‘elif’ is equivalent to ‘else if’ in python.
We keep track of the two previous items by updating variables a and b and using them to generate the next value in the series in image 2.
Now let’s see how to find the kth odd number in Fibonacci series efficiently. This one is trickier and cooler. If we take out those odd numbers and pay attention we find a pattern. The following image shows this process. The order means their relative order to each other and is equal to k so order of 3 in image 3 means third odd number(k=3) in the Fibonacci series. The formulas are the same but the starting pairs are different.
When finding the kth odd number of Fibonacci series if k is odd we consider orange and should find the number with index (k//2) in the orange series. If k is even we consider the green and should find the number with index ((k/2)-1) in the green series. This way we just need either green or orange numbers of Fibonacci series up to that point and it reduces run time significantly when the given k is large.
This is the code for it:
In line 2 function raises error if input is not integer.
Thanks for reading.
This is the link to previous part: