diff options
author | Haidong Ji | 2018-08-27 22:01:02 -0500 |
---|---|---|
committer | Haidong Ji | 2018-08-27 22:01:02 -0500 |
commit | b22465f0b0113e11d301c244fb05c4995358b5db (patch) | |
tree | aa128bd09f9f670626c66f4121f2d8941f06010c /AlgoDesignAndTechniqueEdxJava/sources | |
parent | c6c5c65f881e9bf67a1bfd62022dbf756b489e8a (diff) |
Last digit of sum of Fibs done!
User of spreadsheet really helped here. I should have thought of adding
rows earlier.
Diffstat (limited to 'AlgoDesignAndTechniqueEdxJava/sources')
-rw-r--r-- | AlgoDesignAndTechniqueEdxJava/sources/LastDigitOfFibSum.java | 38 |
1 files changed, 38 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)); + } +} |