course on Kotlin Coding Test, Finding Cichlid Numbers

Hello, everyone! In this lecture, we will solve the problem of finding “binary friends” using Kotlin. A binary friend is a sequence made up of 0s and 1s that satisfies the condition of alternating ‘0’s and ‘1’s. This problem can be efficiently solved using dynamic programming techniques.

1. Problem Definition

The problem of finding binary friends can be defined as follows:

Given an integer N, find the number of binary friends with length N.

Examples

  • N = 1: The binary friends are “0”, “1” → Count: 2
  • N = 2: The binary friends are “00”, “01”, “10”, “11” (but ’00’ is not a binary friend, so it is excluded) → Count: 1 (only 01 and 10 are possible)
  • N = 3: The binary friends are “001”, “010”, “100”, “101”, “110” → Count: 5

2. Understanding the Problem

To solve this problem, it is essential to understand how binary friends are structured. Binary friends have the following conditions:

  1. It cannot start with 0.
  2. 0 cannot appear consecutively more than 2 times.
  3. 1 cannot appear consecutively more than 2 times.

Thus, when the length N of the binary friends is given, if the last digit is 0, the preceding digit must be 1. Conversely, if the last digit is 1, the preceding digit can be either 0 or 1, but the conditions for it to be a binary friend must still be maintained.

3. Dynamic Programming Approach

This problem can be efficiently solved through dynamic programming. We will construct an array divided into two states. Here:

  • dp[i] represents the number of binary friends of length i.
  • dp0[i] represents the number of binary friends of length i that end with 0.
  • dp1[i] represents the number of binary friends of length i that end with 1.

Recurrence Relation

Therefore, we can establish the following recurrence relations:

  • dp0[i] = dp1[i-1]
  • dp1[i] = dp0[i-1] + dp1[i-1]
  • dp[i] = dp0[i] + dp1[i]

Initial Values

The initial values are as follows:

  • dp[1] = 2 (binary friends are 0 and 1)
  • dp0[1] = 1 (case that ends with 1)
  • dp1[1] = 1 (case that ends with 0)

4. Code Implementation

Now, let’s implement the code to find binary friends using Kotlin.


fun countBinaryFriends(n: Int): Int {
    if (n == 1) {
        return 2
    }
    
    val dp0 = IntArray(n + 1)
    val dp1 = IntArray(n + 1)
    
    dp0[1] = 1
    dp1[1] = 1
    
    for (i in 2..n) {
        dp0[i] = dp1[i - 1]
        dp1[i] = dp0[i - 1] + dp1[i - 1]
    }
    
    return dp0[n] + dp1[n]
}

fun main() {
    val n = readLine()!!.toInt()
    println(countBinaryFriends(n))
}

5. Code Explanation

The above code defines a function countBinaryFriends to find binary friends of length N. It takes an integer N as input and returns the count of binary friends related to it. It first handles the case for length 1, then updates the arrays dp0 and dp1 using dynamic programming. Finally, it sums dp0[n] and dp1[n] to return the result.

6. Time Complexity

The time complexity of this algorithm is O(N). It calculates values by traversing the array once, making it efficient. The space complexity is also O(N), allowing dynamic memory management for finding binary friends.

7. Conclusion

Through this lecture, we solved the problem of finding binary friends using Kotlin. This problem is a good example for understanding dynamic programming and is one of the frequently asked problems in practical coding tests. If you know the basic principles of dynamic programming and can apply them, it will enhance your ability to approach and solve various problems.

I hope to continue solving various algorithm problems together and improve coding skills. Thank you!