[Challenge] Fibonacci Finder

Code Challenge #11: June 21, 2017

Every week, we feature the type of brain-teasing question that might be asked in a full-stack developer’s job interview at places such as Google and Facebook.

This week’s challenge is a very common interview question and was reported to have been asked in interviews at many top companies including Google:


Basic Difficulty

Write a function, fibonacciFinder50, that will find the 50th number in the Fibonacci Sequence.

  • Function Name: fibonacciFinder50
  • Input: There are no parameters to this function
  • Output: an integer, the 50th number in the Fibonacci Sequence
  • Example: fibonacciFinder50() => 7778742049
  • In the Fibonacci Sequence, the first two numbers are 0 and 1 and every number thereafter is the sum of the previous two numbers in the sequence
  • For this challenge, consider 0 to be the 1st Fibonacci Number, not the 0th (i.e. do not zero-index)
Find out more about basic challenges.

Intermediate difficulty

Write a function, fibonacciFinderN, that will find the nth number in the Fibonacci Sequence.

  • Function Name: fibonacciFinderN
  • Input: any integer, n, where n is a natural number (in this case not including 0)
  • Output: an integer, the nth number in the Fibonacci Series
  • Example: fibonacciFinderN(300) => 137347080577163115432025771710279131845700275212767467264610201
  • Please use this example – the 300th Fibonacci Number – with your submission
Find out more about intermediate challenges.

Hard Difficulty

Write fibonacciFinderN as efficiently as possible.

  • Can you solve this challenge in O(n) time complexity?
  • Many of you will still find that this challenge is too easy (and this is not unusual), so see how you can stretch yourself further. Can you solve this problem in an unorthodox or elegant way? How about in a different language? Take this opportunity to show off your scripting skills and creative outside-the-box thinking!
Find out more about hard challenges and Big O

Reply to this thread with a link to your code on repl.it and paste your properly formatted code to participate! Don’t just submit your code, remember to explain your solution, too! If you want to be considered as the winner, your function must have the correct name and provide output in the format specified above, you also need to abide by our other simple rules.

As always solutions using imports to do all the heavy lifting such as itertools will not be considered for the winner.


The fine print:

Click the links to find out more about:

Hard
This is solved pretty straight on with Python3. Now to explore some alternative ways maybe!
https://repl.it/IwYR/0

def fibonacciFinderN(n):

    # if n < 1, n is rejected
    if n < 1:
        return

    # if n == 1, 0 is returned right away because the initial state of x, y, z already
    # move the sequence past n == 1
    if n == 1:
        return 0

    x = 0
    y = 1
    z = 1
    i = 3

    # Here the while loop will do a single pass for 1-n, while accumulating the fibonacci number
    # and thus making the algorithm directly proportional with the size of n.
    # This makes the time complexity O(n).

    while i <= n:
        z = x + y
        x = y
        y = z

        i += 1

    return z


print(fibonacciFinderN(300))
4 Likes

Here’s my quick resolution using Python for the Basic and Intermediate difficulties. Now I gotta work on ways to optimise them :slight_smile:

Link to my repl.it resolution: https://repl.it/Iw9c/3

#Basic difficulty
#simply execute the Fibbonnaci Sequence until the 50th number is found

def fibonacciFinder50():
    fibonacci_number = 2 #this variable will show the place of the current fibonacci_number in the sequence of results; in this case what matter is when this variable reaches 50; it starts at 2 because we already know the 1st and 2nd numbers of the sequence: 0 and 1
    
    a = 0 #first value of the sequence 
    b = 1 #second value of the sequence
    c = b #holds the value of b
    
    while fibonacci_number != 50:
        fibonacci_number += 1 #increment the count along with getting the next fibonacci number
        b += a #b just gets added the current value of a
        a = c #a becomes the previous value of b; which is held in c
        c = b #now "reset" c to the current value of b
    else:
        return b #in this case it returns the 50th number in the Fibbonnaci Sequence
    
print('fibonacciFinder50() =>', fibonacciFinder50())

#Intermediate difficulty
#basically the same as basic difficulty, except the sequence is executed until the nth number is found, in this example it's the 300th number 

def fibonacciFinderN(n):
    fibonacci_number = 2 #this variable will show the place of the current fibonacci_number in the sequence of results; in this case what matter is when this variable reaches 50; it starts at 2 because we already know the 1st and 2nd numbers of the sequence: 0 and 1
    
    a = 0 #first value of the sequence 
    b = 1 #second value of the sequence
    c = b #holds the value of b
    
    if n < 1: #if n is lower than 1 prompt the user for another n until n is 1 or higer
        while n < 1:
            n = int(input('That\'s not a valid number. Choose a number higher than 1. '))
    if n == 1:
        return a
    elif n == 2:
        return b 
    else:
        while fibonacci_number != n:
            fibonacci_number += 1 #increment the count along with getting the next fibonacci number
            b += a #b just gets added the current value of a
            a = c #a becomes the previous value of b; which is held in c
            c = b #now "reset" c to the current value of b
        else:
            return b #in this case it returns the 50th number in the Fibbonnaci Sequence
    
print('fibonacciFinderN(300) =>', fibonacciFinderN(300))

Here’s the JavaScript answer to the hard challenge EDIT 4: Produced actual number w/o exponent!

https://repl.it/Iwlq/10

// Hard difficulty
// Even though most every recursive lesson works on the Fib sequence
// it is much more efficient AND easier to solve this problem with
// a simple for loop.

function fibonacciFinderN(n) {
    "use strict";
    let pre = 0,    // Fib(1)
        cur = 1,    // Fib(2)
        fib = 0;    // Usually 'next' but given a semantic name here
        
    // an n of 0 will return early
    if (n === 0) return;
    
    // an n of 1 will return '0'
    // an n of 2 will return '1'
    if (n === 2) return cur;

    // this solution is similar to array.prototype.reduce
    // 'i' starts at 2 since our first two fibs are provided
    for (let i = 2; i < n; i++) {
        fib = pre + cur;
        pre = cur;
        cur = fib;
    }

    return stringIt(fib);
}

function stringIt(num) {
  "use strict";
  let n = num,    // n starts as full number and is shaved down
      x = 0,      // x becomes the digit shaved and added to string
      s = "";     // the string accumulator
  
  while(n > 0) {
    x = n % 10;             // get the ones digit
    s = x + s;              // prepend it to the string accumulator
    n = Math.trunc(n / 10); // shave/shift the number by one digit
  }
  
  return s;
}

console.log(fibonacciFinderN(300));

I’ve been working on learning C++ but don’t yet know how to implement a large enough integer to output the 300th fib. Here is my C++ solution though it still cannot express large enough numbers.

EDIT: apparently my comments weren’t in the initial link.

EDIT 3: Upon being prompted I have reviewed the submission guidelines and adapted my answer accordingly.

EDIT 4: Ok, I think I have finally conformed to the submission requirements.

1 Like

Python

https://repl.it/IwpB

# There is no reason to calculate a constant
def fibonacciFinder50():
    return 7778742049
    

def fibonacciFinderN(N):
    a,b,n = 0,1,2
    if N==1:
      return a
    
    if N==2:
      return b
      
    if N>50:
      a,b,n=4807526976,7778742049,50
      
    while n < N:
        a,b,n = b,a+b,n+1
    return b
print 'fibonacciFinder50() =>', fibonacciFinder50()
print 'fibonacciFinderN(300) =>', fibonacciFinderN(300)
2 Likes

Hard
Javascript

https://repl.it/IwvB/7

function fibonacciFinderN(n) {
  if( typeof n !== "number" || n%1 !== 0 || n <= 0 ) return;
  let [last, fib] = [0, 1];
  for( let i = 2, next = 0; i < n; i++ ) {
    next = fib + last;
    last = fib;
    fib = next;
  }
  return n > 1 ? fib : 0;
}

console.log(fibonacciFinderN(103)); // last with regular notation
console.log(fibonacciFinderN(300));

I’m assuming that first number is 0, so fibonacciFinderN(1) is equal to 0.

Instead of using recursion, which was very slow I decided to use a simple for loop to run n times and calculate each fibonacci number up to N-th. This function also checks if user input is actually integer.

I would add this challenge to any JavaScript programmers to output the true fibonacci number for the 104th term and above.

103 927372692193079200000
104 1.5005205362068963e+21

Looking forward to your findings.

Edit

It will help to have to two before it…

101 354224848179262000000
102 573147844013817200000

It could mean doing digit by digit math on two strings to create the mathematical result in a thrid string. Long additon on strings, as it were.

Edit

function fib(n) {
  let a = 0;
  let b = 1;
  let f = '';
  let i = 2;
  let c;
  while (i++ < n) {
    c = a + b;
    a = b;
    b = c;
    console.log(i,c);
  }
  /* accurate to 15 digits
  x = c;
  while (x > 0) {
    f = (x % 10).toString(10) + f;
    x = Math.floor(x / 10);
  }
  return [f, c, i];
  */
  return c;
}
console.log(fib(104));

The code above generated our example. In comments is the modulo discovery of the number which proves out the limitations of natural tracking. Stings are the only sure way to preserve integrity.

3 Likes

I would argue that it is the purpose of this question… To find that constant. Aren’t all Fibonacci numbers constant, after all?

4 Likes

Basic difficulty in Java https://repl.it/IwyZ/11

class Fibonacci{
  public void fibonacciFinder50(){
    long n=0, m=1,x=0;
    for(int i=0;i<50;i++){
      if(i<=1)
      x=i;
      else{
        x=n+m;
        n=m;
        m=x;
      }
    }
    System.out.println(x);
  }
}
class Main{
  public static void main(String[]args){
    Fibonacci f = new Fibonacci();
    f.fibonacciFinder50();
  }
}
2 Likes

Everybody, please read the posting guidelines to this challenge. Your formatted (markdown) code must be in the submission. The repl.it link is only so readers can explore. Please precede the link with at least one space or some text so the applet does not have to download. Thanks.

4 Likes

Intermediate difficulty in Java https://repl.it/Iwzr/9

class Fibonacci{
  public void fibonacciFinderN(int N){
    double n=0, m=1,x=0,i;
    for(i=0;i<N;i++){
      if(i<=1)
      x=i;
      else{
        x=n+m;
        n=m;
        m=x;
      }
    }
    System.out.println(x);
  }
}
class Main{
  public static void main(String[]args){
    Fibonacci f = new Fibonacci();
    f.fibonacciFinderN(300);
  }
}

Update:

Math Behind:
If you workout the formula for f3 to f11 as a function of f1 & f2, e.g.
f3 = f1+f2
f4 = f3 + f2 = (f1+f2) + f2 = f1 + 2f2
f5 = f4 + f3 = (f1 + 2
f2) + (f1+f2) = 2f1+3f2

f11 = 34f1 + 55f2
f12 = 55f1 + 89f2

This means that, given f1 & f2, f11 & f12 can be obtain using formula above
Notice that, f12 = 55 * f1 + 89 * f2
55 = #11 Fibonacci Number
89 = #12 Fibonacci Number

Meaning:
F(n+10) = F(11) * F(n-1) + F(12) * F(n)

Thus, using same concept:
F(n+100) = F(101) * F(n-1) + F(102) * F(n)
F(n+1000) = F(1001) * F(n-1) + F(1002) * F(n)

The Code:

  1. Do 1000 steps/loop
  2. Then do 100 steps/loop
  3. Then 10 steps/loop
  4. Then solve in 1 step

Therefore:
fibonacciFinderN(12345) only take 12 + 3 + 4 = 20 loop

https://repl.it/IxE6/5

from __future__ import division

def fibonacciFinder50():
    return fibonacciFinderN(50)

def fibonacciFinderN(N):
    a,b,n = 0,1,1
    while N-n >= 1000:
        n +=1000
        #a,b=#f1001, f1002
        a,b=( 26863810024485359386146727202142923967616609318986952340123175997617981700247881689338369654483356564191827856161443356312976673642210350324634850410377680367334151172899169723197082763985615764450078474174626 * a + 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875 *b) , ( 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875 * a  + 70330367711422815821835254877183549770181269836358732742604905087154537118196933579742249494562611733487750449241765991088186363265450223647106012053374121273867339111198139373125598767690091902245245323403501 * b )
    while N-n >= 100:
        n +=100
        #a,b=#f101, f102
        a,b=( 218922995834555169026 * a + 354224848179261915075 *b) , ( 354224848179261915075 * a  + 573147844013817084101 * b )
        
    while N-n >= 10:
        n +=10
        #a,b=#f11, f12
        a,b=(34*a + 55*b),(55*a + 89*b)
        
    d=N-n
    if d == 0:
      return a
    elif d == 1:
      return b
    elif d == 2:
      return a+b
    elif d == 3:
      return a+2*b
    elif d == 4:
      return 2*a+3*b
    elif d == 5:
      return 3*a+5*b
    elif d == 6:
      return 5*a+8*b
    elif d == 7:
      return 8*a+13*b
    elif d == 8:
      return 13*a+21*b
    else:
      #d == 9:
      return 21*a+34*b

print 'fibonacciFinder50() =>', fibonacciFinderN(50)
print 'fibonacciFinderN(300) =>', fibonacciFinderN(300)
f100k  =fibonacciFinderN(100000)
f100kp1=fibonacciFinderN(100001)
print 'Ratio : %0.12f' % (f100kp1 / f100k)

Hard challenge
I used a basic recursive function in C++. :slight_smile:

https://repl.it/IxIb

Here is my submission for all difficulties, Python 3:

I initially considered a recursive solution, as being more intuitive.
After all the Fibonacci formula is; F(n) = F(n-1) + F(n-2).
But I dismissed it as being too inefficient.

I went with the following ( O(N), I believe ) iterative solution instead :

def fibonacciFinder50():
    a,b = 1,0
    for i in range(49):
        a,b = a+b,a
    return b
        
def fibonacciFinderN(n):
    a,b = 1,0
    for i in range(n-1):
        a,b = a+b,a
    return b
    
print("fibonacciFinder50()=")
print(fibonacciFinder50() )
print("fibonacciFinderN(300)=")
print(fibonacciFinderN(300) )

I realize that there is an unused addition, a+b in the last iteration,
But I find this acceptable compared to adding more complication to avoid it.

https://repl.it/IxVE/13

Thanks @mtf for the tip about adding a space before the link.

Python 3 for Basic, Intermediate, and Hard difficulty

# Make algorithm to find fibonacci 50
def fibonacciFinder50():
    # Create counter
    z = 1
    # Start the fibonacci sequence
    x = 0
    y = 1
    # Loop through while less than 50
    while z < 50:
        # Make x = y at the same time that y = x + y, and increase counter by 1
        x, y, z = y, x + y, z + 1
    # Return fibonacci at index 50
    return x

fibonacciFinder50()
print(fibonacciFinder50())

# Make algorithm to find fibonacci 50
def fibonacciFinderN(n):
    # Start the fibonacci sequence
    x = 0
    y = 1
    # Loop through while number is greater than 1 because of index starting at 1 instead of 0
    while n > 1:
        # Make x = y at the same time that y = x + y, and decrease n by 1
        x, y, n = y, x + y, n - 1
    # Return fibonacci at index n
    return x

fibonacciFinderN(300)
print(fibonacciFinderN(300))


https://repl.it/Ixkh/1

Basic Difficulty Python 3

#fibonacciFinder50 finds the 50th number in the fibonacci sequence
#(where 0 is the first number)

def fibonacciFinder50():
	z = 0 #arbitrary counter
	seq = [0, 1]
	while z < 48: #first two given thus stops after 48 loops
		seq.append(seq[z] + seq[z+1]) #creates a running sum
		z += 1
	return seq[-1]
		
print(fibonacciFinder50())

This was a pretty straightforward program to write. I would also just like to say I really enjoy these math based challenges!

https://repl.it/IxxE/4

Intermediate Difficulty Python 3

from time import time

#fibonacciFinderN finds the Nth number in the Fibonacci sequence
#(where 0 is the first number)

def fibonacciFinderN(n):
	z = 0 #arbitrary counter
	seq = [0, 1]
	while z < n - 2: #first two given thus stops after 48 loops
		seq.append(seq[z] + seq[z + 1]) #creates a running sum
		z += 1
	return seq[-1] 

start = time()
f = fibonacciFinderN(100)
end = time()

print("Function1: %s\nTime: %s" % (f, end - start))
```

Thank you @b-twin looking at your code in the last challenge I learned how to test run time and format it how I liked. Again, a pretty straightforward program to write.

 https://repl.it/IxyG/7

Hard difficulty in Java
I used the golden ratio to solve the challenge. the complexity depends on how efficient Math.pow() is.
It seems to overflow for large values due to that function though.

https://repl.it/IyFL/3

public class Main
{
  public static final double phi = 1.61803398875;
  public static void main(String[] args)
  {
    System.out.println(fibonacciFinderN(49));
  }
  public static long fibonacciFinderN(int n)
  {
    n--;
    return (long)(Math.pow(phi,n)/Math.sqrt(5)-Math.pow(1-phi,n)/Math.sqrt(5));
  }
}
1 Like

Just in case the basic solution was mandatory, here it is in relation to my above submission:

https://repl.it/Iwlq/13

function fibonacciFinder50() {
  "use strict";
  return fibonacciFinderN(50);
}
console.log(fibonacciFinder50());

And here is the basic in C++:

https://repl.it/IwnC/11

#include<iostream>

using namespace std;

// This will work for the 50th Fibonacci number but an unsigned long
// long int is not large enough for the 300th.

long int fibonacciFinder50()
{
    long int pre = 0;
    long int cur = 1;
    long int fib = 0;
    
    for (int i = 2; i < 50; ++i) {
        fib = pre + cur;
        pre = cur;
        cur = fib;
    }

    return fib;
}

int main()
{
    cout << fibonacciFinder50() << '\n';

    return 0;
}
1 Like

Intermediate, Python 3
I started with the list[None, 0, 1] so the list index will match the number in the fibonacci sequence(not necessary but makes the code look nicer) , then I just added the last two numbers in the list and appended that to the end of the list and repeated until I reach the fibonacci number I need.

def fibonacciFinderN(n):
    """Returns nth item in fibonacci sequence"""
    # started list with None to imitate the list starting with index 1 so fibonacci_list[1] and the first fibonacci number will match up
    fibonacci_list = [None, 0, 1]
    # if n <= 2, return the value already in the table
    if n <= 2:
        return fibonacci_list[n]
    while len(fibonacci_list) <= n:
        # adds the last two items in fibonacci_list then appends the sum to the list
        fibonacci_list.append(fibonacci_list[-1] + fibonacci_list[-2])
    return fibonacci_list[n]


print(fibonacciFinderN(300))

https://repl.it/IxyG/8

1 Like