Swift Coding Test Course, Making an Integer 1

Coding tests are an important factor in assessing abilities as a software engineer. This article will address an algorithm problem that can be implemented in Swift with the topic “Making an Integer 1” and provide a detailed explanation of the solution process.

Problem Description

We aim to make a given integer x equal to 1 by applying the following rules:

  • x = x - 1 (subtract 1)
  • x = x / 2 (divide by 2, only if x is even)
  • x = x / 3 (divide by 3, only if x is a multiple of 3)

Write a program to calculate the minimum number of operations needed to make x equal to 1 using the above three operations.

Input Format

The first line contains the integer x (1 ≤ x ≤ 106).

Output Format

Output the minimum number of operations required to make the integer 1.

Example

Input:
10

Output:
3

Explanation:
10 → 9 → 3 → 1 (3 operations)

Approach to Solve the Problem

This problem can be attempted using Dynamic Programming. The state of the problem is the current integer x, and we can solve how to make it 1 by using previous states.

By using memoization, we can avoid duplicate calculations, and we can efficiently solve the problem by storing the minimum number of operations needed for each state.

Algorithm Plan

  1. Create an array dp to store the minimum number of operations for all numbers from 1 to x.
  2. Set the initial state dp[1] to 0 (1 is already 1).
  3. Use a loop to iterate from 2 to x:
    • dp[i] = dp[i-1] + 1 (the case of subtracting 1)
    • If i is divisible by 2, then dp[i] = min(dp[i], dp[i/2] + 1) (the case of division by 2)
    • Similarly, if i is divisible by 3, then dp[i] = min(dp[i], dp[i/3] + 1) (the case of division by 3)
  4. Finally, output dp[x].

Swift Implementation Code


import Foundation

func minOperationsToOne(_ x: Int) -> Int {
    var dp = Array(repeating: Int.max, count: x + 1)
    dp[1] = 0
    
    for i in 2...x {
        dp[i] = dp[i - 1] + 1 // -1 operation
        
        if i % 2 == 0 {
            dp[i] = min(dp[i], dp[i / 2] + 1) // /2 operation
        }
        
        if i % 3 == 0 {
            dp[i] = min(dp[i], dp[i / 3] + 1) // /3 operation
        }
    }
    
    return dp[x]
}

let input = Int(readLine()!)!
print(minOperationsToOne(input))

Performance Evaluation

The time complexity of this algorithm is O(n). n is the given integer x. Since it considers a maximum of 3 operations for each integer, it is efficient.

The space complexity is O(n), as it uses the dp array to store all states. This can require a considerable amount of memory, so further optimization may be necessary depending on the needs.

Conclusion

The algorithm problem of making an integer 1 demonstrates the basic principles of dynamic programming well. By solving this problem, one can enhance their understanding of Swift coding tests and learn how to apply dynamic programming techniques.

Through the process of solving the problem, you can develop an understanding of each operation and cultivate a thought process to find the optimal solution. It is advisable to test the algorithm’s performance with various input values and also consider error handling and various optimization methods.

The problem of “Making an Integer 1” discussed in this article is a type that may frequently appear in real coding tests, so it is recommended to practice sufficiently to master it.