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 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