[Kotlin] Korean Coding Test - Programmers - Fibonacci Number

Kotlin

Language :

Question

Link

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)

민갤

Back-End Developer

백엔드 개발자입니다.