# 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)

```
123456789101112131415161718192021222324252627282930313233343536373839404142package 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:

```
123456789101112131415161718192021222324252627282930313233343536373839404142434445package 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]);
}
}
}

```