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)

[cc lang="java" escaped="true"]
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;
	}
}
[/cc]

TestNG test cases for this problem which all passed:

[cc lang="java" escaped="true"]
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]);	
		}
	}
}
[/cc]