101 Logo
onenoughtone

Code Implementation

2 Keys Keyboard Implementation

Below is the implementation of the 2 keys keyboard:

solution.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
/**
 * Find the minimum number of operations to get n 'A's.
 * Dynamic Programming approach.
 *
 * @param {number} n - The target number of 'A's
 * @return {number} - The minimum number of operations
 */
function minSteps(n) {
  // Initialize dp array
  const dp = new Array(n + 1).fill(Infinity);
  dp[1] = 0;  // We start with one 'A'
 
  for (let i = 2; i <= n; i++) {
    for (let j = 1; j < i; j++) {
      if (i % j === 0) {
        dp[i] = Math.min(dp[i], dp[j] + (i / j));
      }
    }
  }
 
  return dp[n];
}
 
/**
 * Find the minimum number of operations to get n 'A's.
 * Prime Factorization approach.
 *
 * @param {number} n - The target number of 'A's
 * @return {number} - The minimum number of operations
 */
function minStepsPrimeFactorization(n) {
  let result = 0;
 
  for (let i = 2; i * i <= n; i++) {
    while (n % i === 0) {
      result += i;
      n /= i;
    }
  }
 
  if (n > 1) {
    result += n;
  }
 
  return result;
}
 
/**
 * Find the minimum number of operations to get n 'A's.
 * Optimized Dynamic Programming approach.
 *
 * @param {number} n - The target number of 'A's
 * @return {number} - The minimum number of operations
 */
function minStepsOptimized(n) {
  // Initialize dp array
  const dp = new Array(n + 1).fill(Infinity);
  dp[1] = 0;  // We start with one 'A'
 
  for (let i = 2; i <= n; i++) {
    for (let j = 1; j * j <= i; j++) {
      if (i % j === 0) {
        dp[i] = Math.min(dp[i], dp[j] + (i / j));
 
        if (j !== i / j) {
          dp[i] = Math.min(dp[i], dp[i / j] + j);
        }
      }
    }
  }
 
  return dp[n];
}
 
// Test cases
console.log(minSteps(3));  // 3
console.log(minSteps(1));  // 0
console.log(minSteps(6));  // 5
 
console.log(minStepsPrimeFactorization(3));  // 3
console.log(minStepsPrimeFactorization(1));  // 0
console.log(minStepsPrimeFactorization(6));  // 5
 
console.log(minStepsOptimized(3));  // 3
console.log(minStepsOptimized(1));  // 0
console.log(minStepsOptimized(6));  // 5

Step-by-Step Explanation

Let's break down the implementation:

  1. Understand the Problem: First, understand that we need to find the minimum number of operations (copy all and paste) to get exactly n 'A's on the screen.
  2. Define the State: Define the state dp[i] as the minimum number of operations to get i 'A's on the screen.
  3. Consider All Options: For each i, consider all possible ways to reach i 'A's by copying and pasting from a smaller number of 'A's.
  4. Optimize the Solution: Optimize the solution by only considering the divisors of i when calculating dp[i], or by using the prime factorization approach.
  5. Handle Edge Cases: Handle edge cases such as n = 1 (return 0, as we already have one 'A' on the screen).
PreviousNext
ProblemSolutionCode
101 Logo
onenoughtone