Improved fib by getting rid of array

Huge improvement in terms of both time and memory consumption.

1 files changed, 17 insertions, 2 deletions

diff --git a/AlgoDesignAndTechniqueEdxJava/sources/FibAgain.java b/AlgoDesignAndTechniqueEdxJava/sources/FibAgain.java
index fbf907e..cef27a5 100644
--- a/AlgoDesignAndTechniqueEdxJava/sources/FibAgain.java
+++ b/AlgoDesignAndTechniqueEdxJava/sources/FibAgain.java
@@ -15,6 +15,21 @@ public class FibAgain {
 		return fibArray[n];
 	}
 
+	public static BigInteger getFibOptimized(int n) {
+		if (n <= 1)
+			return BigInteger.valueOf(n);
+		final BigInteger[] fibArray = new BigInteger[n + 1];
+		BigInteger firstFib = BigInteger.valueOf(0);
+		BigInteger secondFib = BigInteger.valueOf(1);
+		BigInteger tempHolder = BigInteger.valueOf(0);
+		for (int i = 2; i < n + 1; i++) {
+			tempHolder = firstFib.add(secondFib);
+			firstFib = secondFib;
+			secondFib = tempHolder;
+		}
+		return secondFib;
+	}
+
 	public static int getPisanoPeriodOptimized(int m) {
 		// this optimized algorithm is obtained through the
 		// discussion starting around 7:30 mark of the following
@@ -47,8 +62,8 @@ public class FibAgain {
 
 	public static int getFibNModM(long n, int m) {
 		int p = getPisanoPeriodOptimized(m);
-		long i =  n % p;
-		BigInteger fib = getFib((int) i);
+		long i = n % p;
+		BigInteger fib = getFibOptimized((int) i);
 		return fib.mod(BigInteger.valueOf(m)).intValue();
 	}