summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorHaidong Ji2018-08-28 20:07:37 -0500
committerHaidong Ji2018-08-28 20:07:37 -0500
commit0c624da482f7941f0b4f6285e2fb48484f862738 (patch)
tree2fc5699c592588d107cbf5acba83a7ba140ed44b
parente3fa94bc66937292fea1c49c677c672e2fdd654a (diff)
Fib sum last digit done!
-rw-r--r--PlaygroundCpp/Sources/Playground.cpp67
1 files 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';
}