Kotlin Coding Test Course, Go Fast with Time Machine

Problem Description

Imagine! You, from the future, decide to travel to a specific time using a time machine. However, this time machine can only operate through a complex algorithm. The problem is to calculate the minimum number of jumps needed to reach the given time.

Problem Definition

Two integers S and E are given. S is the starting time and E is the arrival time. The time machine operates according to the following rules:

  • From the current time, you can jump to the next time by performing +1, +2, or *2 operations.
  • Write a program to calculate and output the minimum number of jumps taken by the time machine to operate.

Input

In the first line, two integers S (1 ≤ S ≤ 105) and E (1 ≤ E ≤ 105) are given.

Output

Output the minimum number of jumps required for the time machine to reach E.

Example

    Input:
    4 7

    Output:
    2

Problem Solving Process

This problem can be solved using the BFS (Breadth-First Search) algorithm. BFS starts from a specific node and explores all nodes connected to it before exploring the nodes of the next layer. In this problem, each time zone can be represented as a node in a graph, while each jump can be represented as an edge.

Step-by-Step Solution

  1. Initialize the Queue: To perform BFS, first initialize the queue. Add the starting time S and the current jump count to the queue.
  2. Visit Array: Create a visit array to record the times that have already been visited. This prevents visiting the same time multiple times.
  3. Perform BFS: Remove a node from the queue and explore the next times by performing all possible jumps. If the next jump reaches the arrival time E, return the current jump count.
  4. Termination Condition: If the queue becomes empty without reaching the arrival time, terminate the jump process.

Code Implementation


fun minJumps(S: Int, E: Int): Int {
    val queue: Queue> = LinkedList()
    val visited = BooleanArray(100001) // maximum time range 100000
    queue.add(Pair(S, 0))
    visited[S] = true

    while (queue.isNotEmpty()) {
        val (currentTime, jumps) = queue.poll()

        // Reached the destination
        if (currentTime == E) {
            return jumps
        }

        // Next possible times
        val nextTimes = listOf(currentTime + 1, currentTime + 2, currentTime * 2)

        for (nextTime in nextTimes) {
            if (nextTime in 1..100000 && !visited[nextTime]) {
                visited[nextTime] = true
                queue.add(Pair(nextTime, jumps + 1))
            }
        }
    }
    return -1 // unreachable case
}

fun main() {
    val input = readLine()!!.split(" ")
    val S = input[0].toInt()
    val E = input[1].toInt()
    println(minJumps(S, E))
}

Time Complexity Analysis

The time complexity of this algorithm is O(n). Since all time zones will be visited once, performing BFS for up to 100,000 nodes is efficient.

Conclusion

In this lecture, we explored how to apply the BFS algorithm to solve the time machine problem and calculate the shortest distance. Understanding and applying the advantages of implementing it in Kotlin as well as the basic principles of BFS will help you in coding tests. In the next session, we will prepare a lecture to explore other problems and more diverse algorithms!