summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorHaidong Ji2018-08-29 16:02:31 -0500
committerHaidong Ji2018-08-29 16:02:31 -0500
commit99b2699a067510ae42a968c760b87c3acd8daa9e (patch)
tree03100477b3515f2e02536de016ceb9f81384bb2f
parentb22465f0b0113e11d301c244fb05c4995358b5db (diff)
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 :)
-rw-r--r--AlgoDesignAndTechniqueEdxJava/sources/LastDigitOfFibSumAgain.java57
-rw-r--r--AlgoDesignAndTechniqueEdxJava/tests/LastDigitOfFibSumAgainTest.java41
2 files changed, 98 insertions, 0 deletions
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));
+ }
+
+}