渚橋

LeetCode 650. 2 Keys Keyboard

LeetCode Notes [55]: Kotlin DP Solution

Problem

2 Keys Keyboard - LeetCode

Approach 1: Dynamic Programming

Intuition

Observations F(n)

• F(1) = 0 | X
• F(2) = 2 | CP | 2 = 1 * 2 => F(1) + 2 = 2
• F(3) = 3 | CPP | 3 = 1 * 3 => F(1) + 3 = 3
• F(4) = 4 | CPPP, CPCP | 4 = 2 * 2 => F(2) + 2 = 4
• F(5) = 5 | CPPPP | 5 = 1 * 5 => F(1) + 5 = 5
• F(6) = 5 | CPPPPP, CPPCP | 6 = 2 * 3 => F(2) + 3 = 5
• F(7) = 7 | CPPPPPP | 7 = 1 * 7 => F(1) + 7 = 7
• F(8) = 6| CPPPPPPP, CPCPCP | 8 = 2 * 4 => F(2) + 4 = 6
• F(9) = 6 |CPPPPPPPP, CPPCPP | 9 = 3 * 3 => F(3) + 3 = 6
• F(10) = 7 | CPPPPPPPPP, CPCPPPP | 10 = 2 * 5 => F(2) + 5 = 7

F(n) = p * q => min_p_q { F(p) + q }

Code

class Solution {
    fun minSteps(n: Int): Int {
        val arr = IntArray(n + 1) { Int.MAX_VALUE }
        arr[1] = 0
        for (num in 2..n) {
            for (j in 1 until num) {
                if (num % j == 0) {
                    val candidate = arr[j] + num / j
                    if (candidate < arr[num]) {
                        arr[num] = candidate
                    }
                }
            }
        }
        return arr[n]
    }
}

Complexity Analysis

• Time Complexity: O(n²)
• Space Complexity: O(n)

Approach 2: Prime Factorization

Intuition

We can break our moves into groups of (copy, paste, ..., paste). Let C denote copying and P denote pasting. Then for example, in the sequence of moves CPPCPPPPCP, the groups would be [CPP][CPPPP][CP].

Say these groups have lengths g_1, g_2, .... After parsing the first group, there are g_1 'A's. After parsing the second group, there are g_1 * g_2 'A's, and so on. At the end, there are g_1 * g_2 * ... * g_n 'A's.

We want exactly N = g_1 * g_2 * ... * g_n. If any of the g_i are composite, say g_i = p * q, then we can split this group into two groups (the first of which has one copy followed by p-1 pastes, while the second group having one copy and q-1 pastes).

Such a split never uses more moves: we use p+q moves when splitting, and pq moves previously. As p+q <= pq is equivalent to 1 <= (p-1)(q-1), which is true as long as p >= 2 and q >= 2.

Algorithm

By the above argument, we can suppose g_1, g_2, ... is the prime factorization of N, and the answer is therefore the sum of these prime factors.

Code

class Solution {
    fun minSteps(n: Int): Int {
        var num = n
        var steps = 0
        var factor = 2
        while (num > 1) {
            while (num % factor == 0) {
                steps += factor
                num /= factor
            }
            factor++
        }
        return steps
    }
}

Complexity Analysis

• Time Complexity: O(sqrt{N}​). When N is the square of a prime, our loop does O(sqrt{N}​) steps.
• Space Complexity: O(1), the space used by steps and factor.

Similar Questions

LeetCode 2521. Distinct Prime Factors of Product of Array

Reference

2 Keys Keyboard - LeetCode