From 99b2699a067510ae42a968c760b87c3acd8daa9e Mon Sep 17 00:00:00 2001
From: Haidong Ji
Date: Wed, 29 Aug 2018 16:02:31 -0500
Subject: Last digit of partial sum done!

Interesting challenge again. Once I figured out that the result should
be SumFn-SumFm-1, things started falling into place :)---
 .../sources/LastDigitOfFibSumAgain.java            | 57 ++++++++++++++++++++++
 .../tests/LastDigitOfFibSumAgainTest.java          | 41 ++++++++++++++++
 2 files changed, 98 insertions(+)
 create mode 100644 AlgoDesignAndTechniqueEdxJava/sources/LastDigitOfFibSumAgain.java
 create mode 100644 AlgoDesignAndTechniqueEdxJava/tests/LastDigitOfFibSumAgainTest.java

(limited to 'AlgoDesignAndTechniqueEdxJava')

diff --git a/AlgoDesignAndTechniqueEdxJava/sources/LastDigitOfFibSumAgain.java b/AlgoDesignAndTechniqueEdxJava/sources/LastDigitOfFibSumAgain.java
new file mode 100644
index 0000000..024e948
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxJava/sources/LastDigitOfFibSumAgain.java
@@ -0,0 +1,57 @@
+import java.util.Scanner;
+
+public class LastDigitOfFibSumAgain {
+
+	final static int FIB_PISANO_PERIOD_FOR_TEN = 60;
+
+	public static int getFibNModM(long n) {
+		long r = n % FIB_PISANO_PERIOD_FOR_TEN;
+		if (r == 0)
+			return 0;
+		int firstN = 0;
+		int secondN = 1;
+		int tempHolder = 1;
+		for (int i = 1; i < r; i++) {
+			tempHolder = (firstN + secondN) % 10;
+			firstN = secondN;
+			secondN = tempHolder;
+		}
+		return secondN;
+	}
+
+	public static int getLastDigit(long n) {
+		if (n <= 1)
+			return (int) n;
+		int result = getFibNModM(n + 2);
+		if (result == 0)
+			return 9;
+		else
+			return result - 1;
+	}
+
+	public static void main(String args[]) {
+		Scanner in = new Scanner(System.in);
+		long m = in.nextLong();
+		long n = in.nextLong();
+
+		System.out.println(getLastDigit(m, n));
+	}
+
+	public static int getLastDigit(long m, long n) {
+		if (m == n)
+			return getFibNModM(n);
+		else {
+			int sumFn = getLastDigit(n);
+			int sumFm;
+			if (m <= 1)
+				sumFm = 0;
+			else
+				sumFm = getLastDigit(m - 1);
+			if (sumFn >= sumFm)
+				return sumFn - sumFm;
+			else
+				return sumFn - sumFm + 10;
+		}
+	}
+
+}
diff --git a/AlgoDesignAndTechniqueEdxJava/tests/LastDigitOfFibSumAgainTest.java b/AlgoDesignAndTechniqueEdxJava/tests/LastDigitOfFibSumAgainTest.java
new file mode 100644
index 0000000..4d1af65
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxJava/tests/LastDigitOfFibSumAgainTest.java
@@ -0,0 +1,41 @@
+import static org.junit.jupiter.api.Assertions.*;
+import org.junit.jupiter.api.Test;
+
+public class LastDigitOfFibSumAgainTest {
+
+	@Test
+	void testLastDigitOfFibSumAgain5_5() {
+		assertEquals(5, LastDigitOfFibSumAgain.getLastDigit(5, 5));
+	}
+
+	@Test
+	void testLastDigitOfFibSumAgain3_7() {
+		assertEquals(1, LastDigitOfFibSumAgain.getLastDigit(3, 7));
+	}
+
+	@Test
+	void testLastDigitOfFibSumAgain10_200() {
+		assertEquals(2, LastDigitOfFibSumAgain.getLastDigit(10, 200));
+	}
+
+	@Test
+	void testLastDigitOfFibSumAgain5_7() {
+		assertEquals(6, LastDigitOfFibSumAgain.getLastDigit(5, 7));
+	}
+
+	@Test
+	void testLastDigitOfFibSumAgain5_8() {
+		assertEquals(7, LastDigitOfFibSumAgain.getLastDigit(5, 8));
+	}
+
+	@Test
+	void testLastDigitOfFibSumAgain5_9() {
+		assertEquals(1, LastDigitOfFibSumAgain.getLastDigit(5, 9));
+	}
+
+	@Test
+	void testLastDigitOfFibSumAgain1_2() {
+		assertEquals(2, LastDigitOfFibSumAgain.getLastDigit(1, 2));
+	}
+
+}
-- 
cgit v1.2.3