Today, we will solve an interesting algorithm problem called ‘Counting Stair Numbers’ using Kotlin. In this tutorial, we will explain the definition of the problem, the rules, the solution strategy, and the process of implementing the code in detail. The topics covered are as follows.
1. Problem Definition
Stair numbers are defined based on the number of digits, and each digit must follow the following rules:
- The difference between the last digit and the one before it must be 1.
- For example, 123, 321, and 456 are stair numbers. However, 122, 200, and 300 are not stair numbers.
Given an integer N, the problem is to find the number of stair numbers consisting of N digits. I will explain how to calculate the output value considering the input value N.
2. Problem Rules
– The maximum number of digits in input is 100, and when N is 1, there are 10 stair numbers including 0 to 9.
– Each digit can be considered a number from 0 to 9, and the first digit cannot be 0.
– As the number of digits increases, the combinations of stair numbers increase.
3. Solution Strategy
This problem can be solved using dynamic programming. The basic idea is to store the number of possible stair numbers for each digit and use it to calculate the number of stair numbers for the next digit.
- For each digit, consider the possible last digit and calculate a new value based on the value from the previous digit.
- For example,
dp[n][digit]is an array that stores the number of stair numbers when the last digit of an n-digit number isdigit. - Therefore,
dp[n][digit]can be calculated as the sum ofdp[n-1][digit-1]anddp[n-1][digit+1].
3.1. Recurrence Relation
The dp array can be constructed using the following recurrence relations.
dp[n][0] = dp[n-1][1]
dp[n][9] = dp[n-1][8]
dp[n][digit] = dp[n-1][digit-1] + dp[n-1][digit+1] (1 <= digit <= 8)
4. Code Implementation
Now, let’s implement the code to solve the problem. Below is the code using Kotlin.
fun countStairNumbers(n: Int): Int {
if (n == 1) return 10 // When N is 1, the stair numbers are from 0 to 9.
val mod = 1000000000 // Modular operation used when outputting the result
val dp = Array(n + 1) { IntArray(10) }
// Initial values
for (j in 1..9) {
dp[1][j] = 1 // The first digit can be from 1 to 9
}
// Constructing the DP array
for (i in 2..n) {
for (j in 0..9) {
if (j == 0) {
dp[i][j] = dp[i - 1][1] // 0 is only possible from 1 in the previous digit
} else if (j == 9) {
dp[i][j] = dp[i - 1][8] // 9 is only possible from 8 in the previous digit
} else {
dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % mod
}
}
}
// Calculating total stair numbers
var result = 0
for (j in 0..9) {
result = (result + dp[n][j]) % mod
}
return result
}
fun main() {
val n = readLine()!!.toInt() // Receiving input value
println(countStairNumbers(n)) // Outputting the stair numbers
}
5. Execution and Results
Running the above code will output the number of stair numbers based on the input N value. Below are the results for some test cases.
- Input: 1 → Output: 10
- Input: 2 → Output: 17
- Input: 3 → Output: 32
It can be confirmed that the number of stair numbers is correctly calculated for each input value.
6. Conclusion
In this tutorial, we used dynamic programming to solve the ‘Counting Stair Numbers’ problem. We examined how to construct the recurrence relations and the DP array during the problem-solving process, and wrote the actual code. Such problems are frequently presented in coding tests, so it is important to practice adequately.
We will continue to tackle various algorithm problems in the future, and hope to help you improve your problem-solving skills through Kotlin. Thank you!