package Common;

/**
 *
 * @author dimitar
 */
public class Common {
    // Recursive Fibonacci computation
    // Running time - O(2^n)
    // Space - O(n)
    public int fibR(int n) {
        if(n < 0) {
            throw new IllegalArgumentException("Must be a non-negative number");
        }        
        if(n == 0) { return 0; }
        if(n == 1) { return 1; }
        return fibR(n - 1) + fibR(n - 2);
    }
    
    // Iterative Fibonacci computation
    // Running time - O(n)
    // Space - O(1)
    public int fibI(int n) {
        if(n < 0) {
            throw new IllegalArgumentException("Must be a non-negative number");
        }
        
        if(n == 0) { return 0; }
        if(n == 1) { return 1; }
        
        int[] a = new int[n + 1];
        a[1] = 1;
        a[2] = 2;
        for(int i = 2; i <= n; i++) {
            a[i] = a[i - 1] + a[i - 2];
        }        
        return a[n];
    }
    
    // Iterative Fibonacci computation v2
    // Runnint time - O(n)
    // Space - O(1)
    public int fibI2(int n) {
        if(n < 0) {
            throw new IllegalArgumentException("Must be a non-negative number");
        }
        
        if(n == 0) { return 0; }
        if(n == 1) { return 1; }
        
		int p1 = 1;
		int p2 = 2;
		int result = 0;
		for(int i = 2; i < n; i++) {
			result = p1 + p2;
			p1 = p2;
			p2 = result;
		}
		return result;
    }
    
    // Cached (Memorization) Fibonacci computation
    // Running time = O(n)
    // Space - O(n)
    // Note - cache size should be configurable
    private int[] cache = new int[100000];
    public int fibM(int n) {
        if(n < 0) {
            throw new IllegalArgumentException("Must be a non-negative number");
        }
        
        if(n == 0) { return 0; }
        if(n == 1) { return 1; }
        
        if(cache[n] != 0) {
            // return cached result
            return cache[n];
        }
        // cache the result
        cache[n] = fibM(n - 1) + fibM(n - 2);
        return cache[n];
    }
}

@@ -1239,18 +1239,24 @@
        %0A
-%09%09
+        
 int p1 =
@@ -1259,18 +1259,24 @@
 p1 = 1;%0A
-%09%09
+        
 int p2 =
@@ -1279,18 +1279,24 @@
 p2 = 2;%0A
-%09%09
+        
 int resu
@@ -1303,18 +1303,33 @@
 lt = 0;%0A
-%09%09
+        %0A        
 for(int 
@@ -1349,18 +1349,24 @@
  i++) %7B%0A
-%09%09
+        
 %09result 
@@ -1376,18 +1376,24 @@
 1 + p2;%0A
-%09%09
+        
 %09p1 = p2
@@ -1394,18 +1394,24 @@
 1 = p2;%0A
-%09%09
+        
 %09p2 = re
@@ -1420,14 +1420,26 @@
 lt;%0A
-%09%09%7D%0A%09%09
+        %7D%0A        
 retu

Update Common.java