summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorHaidong Ji2018-08-27 22:01:02 -0500
committerHaidong Ji2018-08-27 22:01:02 -0500
commitb22465f0b0113e11d301c244fb05c4995358b5db (patch)
treeaa128bd09f9f670626c66f4121f2d8941f06010c
parentc6c5c65f881e9bf67a1bfd62022dbf756b489e8a (diff)
Last digit of sum of Fibs done!
User of spreadsheet really helped here. I should have thought of adding rows earlier.
-rw-r--r--AlgoDesignAndTechniqueEdxJava/sources/LastDigitOfFibSum.java38
-rw-r--r--AlgoDesignAndTechniqueEdxJava/tests/LastDigitOfFibSumTest.java27
2 files changed, 65 insertions, 0 deletions
diff --git a/AlgoDesignAndTechniqueEdxJava/sources/LastDigitOfFibSum.java b/AlgoDesignAndTechniqueEdxJava/sources/LastDigitOfFibSum.java
new file mode 100644
index 0000000..0783154
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxJava/sources/LastDigitOfFibSum.java
@@ -0,0 +1,38 @@
+import java.util.Scanner;
+
+public class LastDigitOfFibSum {
+
+ 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 n = in.nextLong();
+
+ System.out.println(getLastDigit(n));
+ }
+}
diff --git a/AlgoDesignAndTechniqueEdxJava/tests/LastDigitOfFibSumTest.java b/AlgoDesignAndTechniqueEdxJava/tests/LastDigitOfFibSumTest.java
new file mode 100644
index 0000000..49df83d
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxJava/tests/LastDigitOfFibSumTest.java
@@ -0,0 +1,27 @@
+import static org.junit.jupiter.api.Assertions.*;
+
+import org.junit.jupiter.api.Test;
+
+public class LastDigitOfFibSumTest {
+ @Test
+ void testLastDigitOfFibSum0() {
+ assertEquals(0, LastDigitOfFibSum.getLastDigit(0));
+ }
+ @Test
+ void testLastDigitOfFibSum1() {
+ assertEquals(1, LastDigitOfFibSum.getLastDigit(1));
+ }
+ @Test
+ void testLastDigitOfFibSum6() {
+ assertEquals(0, LastDigitOfFibSum.getLastDigit(6));
+ }
+ @Test
+ void testLastDigitOfFibSum9() {
+ assertEquals(8, LastDigitOfFibSum.getLastDigit(9));
+ }
+ @Test
+ void testLastDigitOfFibSum100() {
+ assertEquals(5, LastDigitOfFibSum.getLastDigit(100));
+ }
+
+}