diff options
author | Haidong Ji | 2018-08-29 16:02:31 -0500 |
---|---|---|
committer | Haidong Ji | 2018-08-29 16:02:31 -0500 |
commit | 99b2699a067510ae42a968c760b87c3acd8daa9e (patch) | |
tree | 03100477b3515f2e02536de016ceb9f81384bb2f /AlgoDesignAndTechniqueEdxJava/sources | |
parent | b22465f0b0113e11d301c244fb05c4995358b5db (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 :)
Diffstat (limited to 'AlgoDesignAndTechniqueEdxJava/sources')
-rw-r--r-- | AlgoDesignAndTechniqueEdxJava/sources/LastDigitOfFibSumAgain.java | 57 |
1 files changed, 57 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; + } + } + +} |