title>Kotlin Coding Test Course: Making an Integer 1

Hello, everyone preparing for the coding test! Today, we will solve the problem of making an integer equal to 1 together. This problem is a great exercise for solidifying the basics of algorithms, and we will solve it using Kotlin.

Problem Description

The problem is to find the minimum number of operations needed to make the integer N equal to 1. The operations that can be used are as follows:

  • If N is divisible by 3, divide N by 3.
  • If N is divisible by 2, divide N by 2.
  • Subtract 1.

For example, when N is 10, the process of 10 -> 9 -> 3 -> 1 requires 3 operations.

Approach to the Problem

To solve this problem, we will use the dynamic programming (DP) technique. DP is a method of solving problems by breaking them down into smaller subproblems. In this case, we will create an array to store the minimum number of operations needed to make each number equal to 1.

Step-by-Step Approach

  1. Array Initialization: Create an array of size equal to the integer N and initialize each index with a default value of -1.
  2. Base Case Setup: Store 0 at index 1 of the array. This indicates that no operations are needed to make it equal to 1.
  3. DP Table Update through a Loop: Use a loop from 2 to N to calculate the minimum number of operations for each number. At this point, we calculate the new values using division operations and subtraction, and store them in the array.
  4. Output the Result: Finally, retrieve the calculated value for N from the main array and output it.

Kotlin Code


fun minOperationsToOne(n: Int): Int {
    // Initialize the dynamic programming table
    val dp = IntArray(n + 1) { Int.MAX_VALUE }
    dp[1] = 0 // 0 operations are needed to make 1 equal to 1

    for (i in 2..n) {
        // Subtract 1
        dp[i] = dp[i - 1] + 1
        
        // Divide by 2
        if (i % 2 == 0) {
            dp[i] = minOf(dp[i], dp[i / 2] + 1)
        }
        
        // Divide by 3
        if (i % 3 == 0) {
            dp[i] = minOf(dp[i], dp[i / 3] + 1)
        }
    }
    return dp[n]
}

fun main() {
    val n = 10 // Test input
    println("Minimum number of operations to make the integer equal to 1: ${minOperationsToOne(n)}")
}

Code Explanation

The above code calculates the minimum number of operations needed to make the given integer N equal to 1. The minOperationsToOne function takes an integer input and uses dynamic programming to find the minimum number of operations. It checks the conditions for each operation to update the possible minimum counts. In particular, dividing by 2 and 3 is checked with conditional statements to perform the operations only when appropriate.

Execution Result

When the above code is executed, it outputs the minimum number of operations required to make the integer equal to 1 for the given input N. For example, when N is 10, the output will be ‘Minimum number of operations to make the integer equal to 1: 3’.

Time Complexity Analysis

The time complexity of this algorithm is O(N). It scans the array once and performs constant-time operations for each operation, allowing for efficient calculations. The space complexity is O(N) because space is required to store the DP array.

Conclusion

Today, we dealt with the problem of making an integer equal to 1. By solving the problem using Kotlin, we were able to learn the basics of dynamic programming. Problems of this type are often presented during job preparation, so it is recommended to practice regularly. I will return with useful content in the next lecture!

References

Thank you!