diff options
Diffstat (limited to 'AlgoDesignAndTechniqueEdxJava/sources/FibLastDigit.java')
-rw-r--r-- | AlgoDesignAndTechniqueEdxJava/sources/FibLastDigit.java | 30 |
1 files changed, 30 insertions, 0 deletions
diff --git a/AlgoDesignAndTechniqueEdxJava/sources/FibLastDigit.java b/AlgoDesignAndTechniqueEdxJava/sources/FibLastDigit.java new file mode 100644 index 0000000..5467782 --- /dev/null +++ b/AlgoDesignAndTechniqueEdxJava/sources/FibLastDigit.java @@ -0,0 +1,30 @@ +import java.util.Scanner; + +public class FibLastDigit { + + public static int lastDigitNaive(int n) { + if (n <= 1) + return n; + return (lastDigitNaive(n - 1) + lastDigitNaive(n - 2)) % 10; + } + + public static int lastDigitOptimized(int n) { + if (n <= 1) + return n; + final int[] fibLastDigitArray = new int[n + 1]; + fibLastDigitArray[0] = 0; + fibLastDigitArray[1] = 1; + for (int i = 2; i < n + 1; i++) { + fibLastDigitArray[i] = (fibLastDigitArray[i - 1] + fibLastDigitArray[i - 2]) % 10; + } + return fibLastDigitArray[n]; + } + + public static void main(String[] args) { + Scanner in = new Scanner(System.in); + int n = in.nextInt(); + + System.out.println(lastDigitOptimized(n)); + } + +} |