FibonacciDemo – Codility – Solution

Java solution to Codility FibonacciDemo problem (PDF) (Lesson 13 – Fibonacci numbers). The problem is to find all the Fibonacci numbers up to a given integer N.

There were two strategies used:

  • a recursive, slower implementation
  • a faster implementation that uses a running sum of the previous two elements to generate the next Fibonacci number

Reference

Fibonacci numbers tutorial (PDF – Codility)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
package com.codility.lesson13.fibonacci;

public class FibonacciDemo {
  public int[] getFibs(int pN) {
    if(pN == 1) { return new int [] { 0 }; }
    if(pN == 2) { return new int [] { 0, 1 }; }
   
    int [] fibs = new int [pN];
    fibs[0] = 0;
    fibs[1] = 1;
    generateFibs(fibs, 2, pN);

    return fibs;
  }
 
  //naive/slowest implementation: fib(n) = fib(n-1) + fib(n-2)
  private void generateFibs(int [] pFibs, int pCurrent, int pMax) {
    int currentFib = pFibs[pCurrent - 1] + pFibs[pCurrent - 2];
    pFibs[pCurrent] = currentFib;

    pCurrent++;
    if(pCurrent == pMax) return;
    else {
      generateFibs(pFibs, pCurrent, pMax);
    }
  }

  //faster implementation - non recursive, uses Fibs of previous 2 elements to calculate current Fib
  public int[] getFibsFast(int pN) {
    if(pN == 1) { return new int [] { 0 }; }
    if(pN == 2) { return new int [] { 0, 1 }; }
   
    int [] fibs = new int [pN];
    fibs[0] = 0;
    fibs[1] = 1;

    for(int i=2; i<fibs.length; i++) {
      fibs[i] = fibs[i-1] + fibs[i-2];
    }
    return fibs;
  }
}

TestNG test cases for this problem which all passed:


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
package test.com.codility.lesson13.fibonacci;

import org.testng.Assert;
import org.testng.annotations.BeforeTest;
import org.testng.annotations.DataProvider;
import org.testng.annotations.Test;

import com.codility.lesson13.fibonacci.FibonacciDemo;

public class FibonacciDemoTests {
  private FibonacciDemo solution;
 
  @BeforeTest
  public void setUp() {
    solution = new FibonacciDemo();
  }

  @DataProvider(name = "data1")
  public Object [][] createData1() {
    return new Object [][] {
      new Object [] { 1,  new int [] { 0 } },
      new Object [] { 3,  new int [] { 0, 1, 1 } },
      new Object [] { 6,  new int [] { 0, 1, 1, 2, 3, 5 } },
      new Object [] { 12, new int [] { 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 } },
    };
  }
 
  @Test(dataProvider = "data1")
  public void verifyGetFibs(int pN, int [] pExpectedFibs) {
    int [] actualFibs = solution.getFibs(pN);
    Assert.assertEquals(actualFibs.length, pExpectedFibs.length);
    for(int i=0; i<pExpectedFibs.length; i++) {
      Assert.assertEquals(actualFibs[i], pExpectedFibs[i]);
    }
  }
 
  @Test(dataProvider = "data1")
  public void verifyGetFibsFast(int pN, int [] pExpectedFibs) {
    int [] actualFibs = solution.getFibsFast(pN);
    Assert.assertEquals(actualFibs.length, pExpectedFibs.length);
    for(int i=0; i<pExpectedFibs.length; i++) {
      Assert.assertEquals(actualFibs[i], pExpectedFibs[i]);
    }
  }
}