From 0c624da482f7941f0b4f6285e2fb48484f862738 Mon Sep 17 00:00:00 2001
From: Haidong Ji
Date: Tue, 28 Aug 2018 20:07:37 -0500
Subject: Fib sum last digit done!

---
 PlaygroundCpp/Sources/Playground.cpp | 67 ++++++++++++++++--------------------
 1 file changed, 29 insertions(+), 38 deletions(-)

diff --git a/PlaygroundCpp/Sources/Playground.cpp b/PlaygroundCpp/Sources/Playground.cpp
index 35ce7da..4445c37 100644
--- a/PlaygroundCpp/Sources/Playground.cpp
+++ b/PlaygroundCpp/Sources/Playground.cpp
@@ -1,55 +1,48 @@
 #include <iostream>
 //#include <gtest/gtest.h>
 
-static int getPisanoPeriodOptimized(int m) {
-	// this optimized algorithm is obtained through the
-	// discussion starting around 7:30 mark of the following
-	// video. We know the upper bound for the loop, which
-	// is 6*m, through articles listed above
-	// https://www.youtube.com/watch?v=Nu-lW-Ifyec
-	// https://en.wikipedia.org/wiki/Pisano_period
-	// The unoptimized naive algorithm looks for modulus
-	// 0 followed by 1
-	int period = 2;
-	int remainder1 = 1;
-	int remainder2 = 1;
+const int FIB_PISANO_PERIOD_FOR_TEN = 60;
 
-	for (int i = 3; i <= 6 * m; i++) {
-		period++;
-		if (remainder2 == 1 && (remainder1 + remainder2 == m)) {
-			break;
-		} else {
-			int tempHolder = remainder1 + remainder2;
-			remainder1 = remainder2;
-			if (tempHolder >= m) {
-				remainder2 = tempHolder - m;
-			} else {
-				remainder2 = tempHolder;
-			}
-		}
-	}
-	return period;
-}
-static int getFibNModM(long n, int m) {
-	int p = getPisanoPeriodOptimized(m);
-	long r = n % p;
+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) % m;
+		tempHolder = (firstN + secondN) % 10;
 		firstN = secondN;
 		secondN = tempHolder;
 	}
 	return secondN;
 }
+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;
+}
 
-//TEST(FibLastDigitTest, Zero) {
-//	ASSERT_EQ(getFibNModM(2015, 3), 1);
+//TEST(FibSumLastDigitTest, Zero) {
+//	ASSERT_EQ(getLastDigit(0), 0);
 //}
-//
+//TEST(FibSumLastDigitTest, One) {
+//	ASSERT_EQ(getLastDigit(1), 1);
+//}
+//TEST(FibSumLastDigitTest, Six) {
+//	ASSERT_EQ(getLastDigit(6), 0);
+//}
+//TEST(FibSumLastDigitTest, Nine) {
+//	ASSERT_EQ(getLastDigit(9), 8);
+//}
+//TEST(FibSumLastDigitTest, OneHundred) {
+//	ASSERT_EQ(getLastDigit(100), 5);
+//}
+
 //TEST(FibLastDigitTest, One) {
 //	ASSERT_EQ(getFibNModM(239, 1000), 161);
 //}
@@ -72,9 +65,7 @@ static int getFibNModM(long n, int m) {
 
 int main() {
 	long n;
-	int m;
 	std::cin >> n;
-	std::cin >> m;
-	int c = getFibNModM(n, m);
+	int c = getLastDigit(n);
 	std::cout << c << '\n';
 }
-- 
cgit v1.2.3