[Kotlin] Korean Coding Test - Programmers - Fibonacci Number
KotlinQuestion
The Fibonacci number is the number that F(n) = F(n-1) + F(n-2) applies to 1 or more n when F(0) = 0, F(1) = 1.
For example
- F(2) = F(0) + F(1) = 0 + 1 = 1
- F(3) = F(1) + F(2) = 1 + 1 = 2
- F(4) = F(2) + F(3) = 1 + 2 = 3
- F(5) = F(3) + F(4) = 2 + 3 = 5
It goes like this.
When more than two ns are entered, complete solution, a function that returns the remainder of the nth Fibonacci divided by 1234567.
Restrictions
n is a natural number that is greater than or equal to 2 and less than 100,000.
Input/Output example
Input/Output example #1
- Input: 3
- Output: 2
Input/Output example #2
- Input: 5
- Output: 5
Solve
n is a maximum of 100,000.
- Recursion calls vary slightly depending on memory size and programming language, but cannot exceed up to 10,000 times.
- Use the for statement to find the Fibonacci sequence.
Find the remainder obtained by dividing the nth Fibonacci number by 1234567
- The Fibonacci number increases exponentially as n increases.
- Use the remaining computational distribution law (A + B) % C ≡ ((A % C) + (B % C)) % C property so that it does not deviate from the data type range.
Code
class Solution {
fun solution(n: Int): Int {
val answer = IntArray(n + 1) { 0 }
answer[1] = 1
for (i in 2..n) answer[i] = (answer[i - 1] + answer[i - 2]) % 1234567
return answer[n]
}
}
TEST 1 〉 Pass (0.01ms, 61MB)
TEST 2 〉 Pass (0.02ms, 62MB)
TEST 3 〉 Pass (0.02ms, 61.2MB)
TEST 4 〉 Pass (0.01ms, 61.1MB)
TEST 5 〉 Pass (0.02ms, 60.7MB)
TEST 6 〉 Pass (0.01ms, 60.2MB)
TEST 7 〉 Pass (0.14ms, 61.7MB)
TEST 8 〉 Pass (0.09ms, 60.8MB)
TEST 9 〉 Pass (0.04ms, 58.3MB)
TEST 10 〉 Pass (0.16ms, 58.6MB)
TEST 11 〉 Pass (0.06ms, 61MB)
TEST 12 〉 Pass (0.04ms, 61.2MB)
TEST 13 〉 Pass (2.49ms, 61.9MB)
TEST 14 〉 Pass (2.81ms, 61.1MB)