From 9633df82de06c9ef6b88bb2068e3fdf19a1554c4 Mon Sep 17 00:00:00 2001
From: Haidong Ji
Date: Tue, 14 Aug 2018 15:47:11 -0500
Subject: Last digit of fib and some renaming refactoring!

---
 .../sources/FibLastDigit.java                      | 30 ++++++++++++++++++++
 .../sources/Fibonacci.java                         | 14 +++++-----
 .../tests/FibLastDigitTest.java                    | 32 ++++++++++++++++++++++
 3 files changed, 69 insertions(+), 7 deletions(-)
 create mode 100644 AlgoDesignAndTechniqueEdxJava/sources/FibLastDigit.java
 create mode 100644 AlgoDesignAndTechniqueEdxJava/tests/FibLastDigitTest.java

(limited to 'AlgoDesignAndTechniqueEdxJava')

diff --git a/AlgoDesignAndTechniqueEdxJava/sources/FibLastDigit.java b/AlgoDesignAndTechniqueEdxJava/sources/FibLastDigit.java
new file mode 100644
index 0000000..5467782
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxJava/sources/FibLastDigit.java
@@ -0,0 +1,30 @@
+import java.util.Scanner;
+
+public class FibLastDigit {
+
+	public static int lastDigitNaive(int n) {
+		if (n <= 1)
+			return n;
+		return (lastDigitNaive(n - 1) + lastDigitNaive(n - 2)) % 10;
+	}
+
+	public static int lastDigitOptimized(int n) {
+		if (n <= 1)
+			return n;
+		final int[] fibLastDigitArray = new int[n + 1];
+		fibLastDigitArray[0] = 0;
+		fibLastDigitArray[1] = 1;
+		for (int i = 2; i < n + 1; i++) {
+			fibLastDigitArray[i] = (fibLastDigitArray[i - 1] + fibLastDigitArray[i - 2]) % 10;
+		}
+		return fibLastDigitArray[n];
+	}
+
+	public static void main(String[] args) {
+		Scanner in = new Scanner(System.in);
+		int n = in.nextInt();
+
+		System.out.println(lastDigitOptimized(n));
+	}
+
+}
diff --git a/AlgoDesignAndTechniqueEdxJava/sources/Fibonacci.java b/AlgoDesignAndTechniqueEdxJava/sources/Fibonacci.java
index 94217ed..53388fe 100644
--- a/AlgoDesignAndTechniqueEdxJava/sources/Fibonacci.java
+++ b/AlgoDesignAndTechniqueEdxJava/sources/Fibonacci.java
@@ -8,16 +8,16 @@ public class Fibonacci {
 		return fib_naive(n - 1) + fib_naive(n - 2);
 	}
 
-	public static long fib_optimized1(int i) {
-		if (i <= 1)
-			return (long) i;
-		final long[] fibArray = new long[i+1];
+	public static long fib_optimized1(int n) {
+		if (n <= 1)
+			return (long) n;
+		final long[] fibArray = new long[n+1];
 		fibArray[0] = 0;
 		fibArray[1] = 1;
-		for (int j = 2; j < i+1; j++) {
-			fibArray[j] = fibArray[j - 1] + fibArray[j - 2];
+		for (int i = 2; i < n+1; i++) {
+			fibArray[i] = fibArray[i - 1] + fibArray[i - 2];
 		}
-		return fibArray[i];
+		return fibArray[n];
 	}
 
 	public static void main(String args[]) {
diff --git a/AlgoDesignAndTechniqueEdxJava/tests/FibLastDigitTest.java b/AlgoDesignAndTechniqueEdxJava/tests/FibLastDigitTest.java
new file mode 100644
index 0000000..4646c62
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxJava/tests/FibLastDigitTest.java
@@ -0,0 +1,32 @@
+import static org.junit.jupiter.api.Assertions.*;
+
+import org.junit.jupiter.api.Test;
+
+public class FibLastDigitTest {
+	@Test
+	void testFibonacci0() {
+		assertEquals(0, FibLastDigit.lastDigitNaive(0));
+		assertEquals(0, FibLastDigit.lastDigitOptimized(0));
+	}
+
+	@Test
+	void testFibonacci1() {
+		assertEquals(1, FibLastDigit.lastDigitNaive(1));
+		assertEquals(2, FibLastDigit.lastDigitNaive(3));
+		assertEquals(1, FibLastDigit.lastDigitOptimized(1));
+		assertEquals(2, FibLastDigit.lastDigitOptimized(3));
+	}
+
+	@Test
+	void testFibonacci40() {
+		assertEquals(5, FibLastDigit.lastDigitNaive(40));
+		assertEquals(5, FibLastDigit.lastDigitOptimized(40));
+		assertEquals(9, FibLastDigit.lastDigitOptimized(331));
+		assertEquals(5, FibLastDigit.lastDigitOptimized(327305));
+//		assertEquals(1, Fibonacci.fib_optimized1(2));
+//		assertEquals(2, Fibonacci.fib_optimized1(3));
+//		assertEquals(3, Fibonacci.fib_optimized1(4));
+//		assertEquals(102334155, Fibonacci.fib_optimized1(40));
+	}
+
+}
-- 
cgit v1.2.3