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)
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
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:
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
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]);
}
}
}