Ugly Number Ii

                                            
class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int> ugly(n);
        ugly[0] = 1;
        int idx2 = 0, idx3 = 0, idx5 = 0;
        int factor2 = 2, factor3 = 3, factor5 = 5;
        
        for (int i = 1; i < n; i++) {
            int minFactor = min({factor2, factor3, factor5});
            ugly[i] = minFactor;
            
            if (factor2 == minFactor) factor2 = 2 * ugly[++idx2];
            if (factor3 == minFactor) factor3 = 3 * ugly[++idx3];
            if (factor5 == minFactor) factor5 = 5 * ugly[++idx5];
        }
        
        return ugly[n - 1];
    }
};

                                            
class Solution {
    public int nthUglyNumber(int n) {
        int[] ugly = new int[n];
        ugly[0] = 1;
        int index2 = 0, index3 = 0, index5 = 0;
        int factor2 = 2, factor3 = 3, factor5 = 5;

        for (int i = 1; i < n; i++) {
            int min = Math.min(Math.min(factor2, factor3), factor5);
            ugly[i] = min;

            if (factor2 == min) {
                factor2 = 2 * ugly[++index2];
            }
            if (factor3 == min) {
                factor3 = 3 * ugly[++index3];
            }
            if (factor5 == min) {
                factor5 = 5 * ugly[++index5];
            }
        }

        return ugly[n - 1];
    }
}

                                            
class Solution(object):
    def nthUglyNumber(self, n):
        ugly = [1]
        i2, i3, i5 = 0, 0, 0
        while len(ugly) < n:
            next_ugly = min(ugly[i2] * 2, ugly[i3] * 3, ugly[i5] * 5)
            ugly.append(next_ugly)
            if next_ugly == ugly[i2] * 2:
                i2 += 1
            if next_ugly == ugly[i3] * 3:
                i3 += 1
            if next_ugly == ugly[i5] * 5:
                i5 += 1
        return ugly[-1]

                                            
int nthUglyNumber(int n) {
    int ugly[n];
    ugly[0] = 1;
    int i2 = 0, i3 = 0, i5 = 0;
    int next_multiple_of_2 = 2;
    int next_multiple_of_3 = 3;
    int next_multiple_of_5 = 5;
    int next_ugly_no = 1;
    
    for (int i = 1; i < n; i++) {
        next_ugly_no = next_multiple_of_2 < next_multiple_of_3 ? (next_multiple_of_2 < next_multiple_of_5 ? next_multiple_of_2 : next_multiple_of_5) : (next_multiple_of_3 < next_multiple_of_5 ? next_multiple_of_3 : next_multiple_of_5);
        ugly[i] = next_ugly_no;
        
        if (next_ugly_no == next_multiple_of_2) {
            i2++;
            next_multiple_of_2 = ugly[i2] * 2;
        }
            
        if (next_ugly_no == next_multiple_of_3) {
            i3++;
            next_multiple_of_3 = ugly[i3] * 3;
        }
            
        if (next_ugly_no == next_multiple_of_5) {
            i5++;
            next_multiple_of_5 = ugly[i5] * 5;
        }
    }
    
    return next_ugly_no;
}

                                            
public class Solution {
    public int NthUglyNumber(int n) {
        if(n<=0) return 0;
        
        int[] ugly = new int[n];
        ugly[0] = 1;
        int index2 = 0, index3 = 0, index5 = 0;
        int factor2 = 2, factor3 = 3, factor5 = 5;
        
        for(int i=1; i<n; i++){
            int min = Math.Min(Math.Min(factor2, factor3), factor5);
            ugly[i] = min;
            
            if(factor2 == min) factor2 = 2 * ugly[++index2];
            if(factor3 == min) factor3 = 3 * ugly[++index3];
            if(factor5 == min) factor5 = 5 * ugly[++index5];
        }
        
        return ugly[n-1];
    }
}

                                            
/**
 * @param {number} n
 * @return {number}
 */
var nthUglyNumber = function(n) {
    let ugly = [1];
    let index2 = 0, index3 = 0, index5 = 0;
    
    while (ugly.length < n) {
        let next = Math.min(ugly[index2] * 2, ugly[index3] * 3, ugly[index5] * 5);
        ugly.push(next);
        
        if (next === ugly[index2] * 2) index2++;
        if (next === ugly[index3] * 3) index3++;
        if (next === ugly[index5] * 5) index5++;
    }
    
    return ugly[n - 1];
};

                                            
function nthUglyNumber(n: number): number {
    const dp: number[] = new Array(n);
    dp[0] = 1;
    
    let p2 = 0, p3 = 0, p5 = 0;
    
    for (let i = 1; i < n; i++) {
        dp[i] = Math.min(dp[p2] * 2, dp[p3] * 3, dp[p5] * 5);
        
        if (dp[i] === dp[p2] * 2) {
            p2++;
        }
        if (dp[i] === dp[p3] * 3) {
            p3++;
        }
        if (dp[i] === dp[p5] * 5) {
            p5++;
        }
    }
    
    return dp[n - 1];
};

                                            
class Solution {
    /**
     * @param Integer $n
     */
    function nthUglyNumber($n) {
        $ugly = [1];
        $i2 = $i3 = $i5 = 0;

        while(count($ugly) < $n) {
            $next = min($ugly[$i2] * 2, $ugly[$i3] * 3, $ugly[$i5] * 5);
            $ugly[] = $next;

            if ($next == $ugly[$i2] * 2) $i2++;
            if ($next == $ugly[$i3] * 3) $i3++;
            if ($next == $ugly[$i5] * 5) $i5++;
        }

        return $ugly[$n - 1];
    }
}

                                            
class Solution {
    func nthUglyNumber(_ n: Int) -> Int {
        var ugly = [1]
        var i = 0, j = 0, k = 0
        
        while ugly.count < n {
            let num2 = ugly[i] * 2
            let num3 = ugly[j] * 3
            let num5 = ugly[k] * 5
            
            let nextUgly = min(num2, num3, num5)
            ugly.append(nextUgly)
            
            if nextUgly == num2 {
                i += 1
            }
            if nextUgly == num3 {
                j += 1
            }
            if nextUgly == num5 {
                k += 1
            }
        }
        
        return ugly[n - 1]
    }
}

                                            
class Solution {
    fun nthUglyNumber(n: Int): Int {
        var ugly = IntArray(n)
        ugly[0] = 1

        var i2 = 0
        var i3 = 0
        var i5 = 0

        var next_multiple_of_2 = 2
        var next_multiple_of_3 = 3
        var next_multiple_of_5 = 5

        for (i in 1 until n) {
            val min = minOf(next_multiple_of_2, next_multiple_of_3, next_multiple_of_5)
            ugly[i] = min

            if (min == next_multiple_of_2) {
                i2++
                next_multiple_of_2 = ugly[i2] * 2
            }

            if (min == next_multiple_of_3) {
                i3++
                next_multiple_of_3 = ugly[i3] * 3
            }

            if (min == next_multiple_of_5) {
                i5++
                next_multiple_of_5 = ugly[i5] * 5
            }
        }

        return ugly[n - 1]
    }
}

                                            
class Solution {
  int nthUglyNumber(int n) {
    List<int> ugly = List.filled(n, 0);
    ugly[0] = 1;
    int idx2 = 0, idx3 = 0, idx5 = 0;
    int factor2 = 2, factor3 = 3, factor5 = 5;

    for (int i = 1; i < n; i++) {
      int min = [factor2, factor3, factor5].reduce((value, element) => value > element ? element : value);
      ugly[i] = min;

      if (min == factor2) {
        idx2++;
        factor2 = ugly[idx2] * 2;
      }
      if (min == factor3) {
        idx3++;
        factor3 = ugly[idx3] * 3;
      }
      if (min == factor5) {
        idx5++;
        factor5 = ugly[idx5] * 5;
      }
    }

    return ugly[n - 1];
  }
}

                                            
func nthUglyNumber(n int) int {
    ugly := make([]int, n)
    ugly[0] = 1
    i2, i3, i5 := 0, 0, 0

    for i := 1; i < n; i++ {
        ugly[i] = min(ugly[i2]*2, min(ugly[i3]*3, ugly[i5]*5))
        
        if ugly[i] == ugly[i2]*2 {
            i2++
        }
        if ugly[i] == ugly[i3]*3 {
            i3++
        }
        if ugly[i] == ugly[i5]*5 {
            i5++
        }
    }
    
    return ugly[n-1]
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

                                            
# @param {Integer} n
# @return {Integer}
def nth_ugly_number(n)
    ugly = [1]
    p2 = p3 = p5 = 0
    while ugly.length < n
        next_ugly = [ugly[p2] * 2, ugly[p3] * 3, ugly[p5] * 5].min
        ugly << next_ugly
        p2 += 1 if ugly[p2] * 2 <= next_ugly
        p3 += 1 if ugly[p3] * 3 <= next_ugly
        p5 += 1 if ugly[p5] * 5 <= next_ugly
    end
    ugly.last
end

                                            
object Solution {
    def nthUglyNumber(n: Int): Int = {
        var ugly = Array.ofDim[Int](n)
        ugly(0) = 1
        var idx2 = 0
        var idx3 = 0
        var idx5 = 0

        for (i <- 1 until n) {
            val next2 = ugly(idx2) * 2
            val next3 = ugly(idx3) * 3
            val next5 = ugly(idx5) * 5

            val nextUgly = next2.min(next3).min(next5)
            ugly(i) = nextUgly

            if (nextUgly == next2) idx2 += 1
            if (nextUgly == next3) idx3 += 1
            if (nextUgly == next5) idx5 += 1
        }

        ugly(n - 1)
    }
}

                                            
(define/contract (nth-ugly-number n)
  (-> exact-integer? exact-integer?)
  (define (ugly? k)
    (or (= k 1)
        (and (zero? (remainder k 2)) (ugly? (quotient k 2)))
        (and (zero? (remainder k 3)) (ugly? (quotient k 3)))
        (and (zero? (remainder k 5)) (ugly? (quotient k 5))))
    )
  
  (let loop ([count 1] [current 1])
    (cond
      [(= count n) current]
      [(ugly? (add1 current)) (loop (add1 count) (add1 current))]
      [else (loop count (add1 current))]
      )
    )
  )

To solve this coding challenge, you need to compute the nth ugly number, where ugly numbers are defined as positive integers that can only be factored by 2, 3, and 5. The problem requires generating these numbers in sequence until you find the nth one. This can be efficiently managed using a dynamic programming-like approach by maintaining an array of ugly numbers. Here is a detailed explanation of the approach:

Explanation

Initialization : Initialize a list with the first ugly number, which is 1 by definition.
Three Pointers : Use three pointers to keep track of the multiples of 2, 3, and 5. Let's call these pointers
i2

,
i3

, and
i5

.
**Next Ugly Number Calculation**: Use the pointers to calculate the next candidate for the ugly number by taking the minimum of the current ugly number multiples (i.e.,
ugly[i2] * 2

,
ugly[i3] * 3

,
ugly[i5] * 5

).
Appending the Next Ugly Number : Append this minimum value to the ugly number list.
Pointer Update : Update the appropriate pointer(s) whenever their corresponding value is used to ensure that the next candidate will come from the next multiple.
Repeat : Repeat steps 3 to 5 until you have generated the nth ugly number.
Return the Result : Finally, return the nth ugly number from the list.

Detailed Steps in Pseudocode

                                            
# Function to find the nth ugly number
FUNCTION findNthUglyNumber(n):
# Initialize an array to store ugly numbers
uglyNumbers = [1]

# Initialize pointers for multiples of 2, 3, and 5
pointer2 = 0
pointer3 = 0
pointer5 = 0

# Continue generating ugly numbers until we have the nth one
WHILE (length of uglyNumbers < n):
# Calculate next candidates for ugly numbers
nextMultipleOf2 = uglyNumbers[pointer2] * 2
nextMultipleOf3 = uglyNumbers[pointer3] * 3
nextMultipleOf5 = uglyNumbers[pointer5] * 5

# Find the minimum of these candidates to be the next ugly number
nextUglyNumber = MIN(nextMultipleOf2, nextMultipleOf3, nextMultipleOf5)

# Append this minimum value to the uglyNumbers list
APPEND nextUglyNumber TO uglyNumbers

# Update the respective pointer(s)
IF nextUglyNumber == nextMultipleOf2:
pointer2 = pointer2 + 1

IF nextUglyNumber == nextMultipleOf3:
pointer3 = pointer3 + 1

IF nextUglyNumber == nextMultipleOf5:
pointer5 = pointer5 + 1

# End WHILE loop

# The nth ugly number will be the last element in uglyNumbers list
RETURN uglyNumbers[n-1]
END FUNCTION

In-depth Explanation of Pseudocode

Initialize Array and Pointers :

uglyNumbers

is initialized with the first ugly number
[1]

.
Pointers
pointer2

,
pointer3

, and
pointer5

are initialized to
0

, pointing to the first index of
uglyNumbers

.

Loop Until nth Ugly Number is Found :

Conversely, the loop runs until the number of ugly numbers generated equals
n

.

Calculate Next Multiples :

nextMultipleOf2

,
nextMultipleOf3

, and
nextMultipleOf5

are calculated by multiplying the current pointed values in the list by 2, 3, and 5 respectively.

Find Minimum Value :

nextUglyNumber

is determined as the smallest value among
nextMultipleOf2

,
nextMultipleOf3

, and
nextMultipleOf5

.

Append to List :

This
nextUglyNumber

is added to the
uglyNumbers

list.

Update Pointers :

Depending on which multiple was chosen as
nextUglyNumber

, the respective pointer (or pointers, in the case of duplicates) is incremented to the next index.

Return nth Ugly Number :

Once the loop completes, the nth ugly number will be at index
n-1

in the 0-indexed list.

This method ensures efficient calculation of the nth ugly number using a dynamic programming approach while maintaining clarity and simplicity in the algorithm.