101 Logo
onenoughtone

Code Implementation

Prime Factor Sequence Implementation

Below is the implementation of the prime factor sequence:

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
/**
 * Dynamic Programming Approach
 * Time Complexity: O(n) - We perform a constant amount of work for each of the n ugly numbers
 * Space Complexity: O(n) - We need to store all n ugly numbers in the dp array
 *
 * @param {number} n - The position of the ugly number to find
 * @return {number} - The nth ugly number
 */
function nthUglyNumber(n) {
  // Initialize the dp array with the first ugly number
  const dp = new Array(n);
  dp[0] = 1;
 
  // Initialize three pointers for multiplying by 2, 3, and 5
  let p2 = 0;
  let p3 = 0;
  let p5 = 0;
 
  // Generate the remaining ugly numbers
  for (let i = 1; i < n; i++) {
    // Calculate the next potential ugly numbers
    const next2 = dp[p2] * 2;
    const next3 = dp[p3] * 3;
    const next5 = dp[p5] * 5;
 
    // Take the minimum of the three potential ugly numbers
    dp[i] = Math.min(next2, next3, next5);
 
    // Update the pointers
    if (dp[i] === next2) {
      p2++;
    }
    if (dp[i] === next3) {
      p3++;
    }
    if (dp[i] === next5) {
      p5++;
    }
  }
 
  // Return the nth ugly number
  return dp[n - 1];
}

Step-by-Step Explanation

Let's break down the implementation:

  1. 1. Understand the Problem: First, understand that we need to find the nth ugly number, where an ugly number is a positive integer whose prime factors are limited to 2, 3, and 5.
  2. 2. Recognize the Pattern: Recognize that every ugly number (except 1) can be generated by multiplying a previous ugly number by either 2, 3, or 5.
  3. 3. Implement the Dynamic Programming Approach: Use dynamic programming to generate the sequence of ugly numbers by maintaining three pointers to track which previous ugly numbers to multiply by 2, 3, and 5.
  4. 4. Implement the Min Heap Approach: Alternatively, use a min heap to efficiently find the next ugly number in the sequence by keeping track of all potential next ugly numbers.
  5. 5. Handle Edge Cases: Consider edge cases such as n = 1, where the answer is 1.
  6. 6. Optimize for Performance: Choose the most efficient approach based on the constraints of the problem.
  7. 7. Test the Solution: Verify the solution with the provided examples and additional test cases.
PreviousNext
ProblemSolutionCode
101 Logo
onenoughtone