diff options
| -rw-r--r-- | PlaygroundCpp/Sources/Playground.cpp | 67 |
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'; } |