Sushant Gaurav

Data Structures and Algorithms

Ugly Numbers

Problem Statement

We are provided with a number n. We need to print the n-th ugly number.

An ugly number is a number whose prime factors are 2, 3, or 5 only.

Note: $1$ is considered as an ugly number (conventionally).

Refer to the Example and Explanation sections for more details and the Approach section to understand how to find the n-th ugly number.

Example

Input number (n) = 7
Output: $7$th ugly number is: $8$

Input number (n) = 15
Output: $15$th ugly number is: $24$

Input number (n) = 10
Output: $10$th ugly number is: $12$

Input number (n) = 150
Output: $150$th ugly number is: $5832$

Example Explanation

Let us take the above example where the input number (n) is 7. To understand how the 7th ugly number is 8, let us first understand the ugly number sequence or series.

The ugly numbers series is: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, …

In this series, we can see the prime factor(s) of every number 2, 3, or 5. In this series, 7, 11, and 13 are not included as ugly because:

  • The prime factor of 7 is 7 only which is not among the 2, 3, or 5.
  • The prime factor of 11 is 11 only which is not among the 2, 3, or 5.
  • Similarly, the prime factor of 13 is 13 only which is not among the 2, 3, or 5.

In this manner, we can continue our searching starting from the number 1 and check whether a certain number’s prime factor(s) is 2/3/5 or not.

Note:
prime factors are the factors of a number that are themselves prime. For example, the factors of 12 are 2, 3, 4, 6, and 12. But only 2 and 3 are prime factors since 2 and 3 are themselves prime.

A prime number is a natural number, other than one, whose factors are 1 and itself only.

Constraints

  • The first input is the number n which denotes that we need to print the nth ugly number.
    • $1 <= n <= 10^{18}$

In some problems, you may find the number of test cases represented by t. So, we only need to call the findUglyNumbers() function t-times.

The problem is to find the n-th ugly number from the ugly number series.

Approach 1 – Naive Approach – Simple Brute-Force

The naive or the brute force approach of finding the n-th ugly number can be running a loop and maintaining a counter that will increase once a number is encountered as an ugly number. We will check every number in the loop starting from 1. The loop will stop when the counter has reached n i.e. we have found our nth ugly number.

Now the idea to check whether a certain number is an ugly number or not, is simple. As we know the prime factors of an ugly number are 2, 3, or 5. So, we can divide the given number with the greatest divisible power of 2, 3, and 5. Now, if the number becomes one ($1$) then we can say that an input number is ugly.

Refer to the next sub-section for the algorithm.

Algorithm

  1. Create a function namely findUglyNumbers() which takes a number n.
  2. Initialize a counter that will increase once a number is encountered as an ugly number.
  3. Run a loop starting from 1 (as 1 is the first ugly number). This loop will terminate only when the counter has reached n, which means that the nth ugly number is found.
  4. Find the maximum divisible powers of 2, 3, and 5 for the ith number using a helper function.
  5. Now, if the ith number is found to be an ugly number then increment the counter.

Refer to the next sub-section for the code implementation in various programming languages.

Code Implementation

Let us see the code for the above-discussed algorithm.

C++ Code

#include <bits/stdc++.h>
using namespace std;

// a function that will divide the dividend by the maximum power of divisor and then return the dividend.
int maximumDivisible(int dividend, int divisor) {
   while (dividend % divisor == 0)
      dividend = dividend / divisor;

   return dividend;
}

// A function that weill check whether the number n is an ugly number or not.
int isUglyNumber(int n) {
   n = maximumDivisible(n, 2);
   n = maximumDivisible(n, 3);
   n = maximumDivisible(n, 5);

   if (n == 1)
      return 1;
   else
      return 0;
}

// a function tha that will find and return the nth ugly number.
int findUglyNumbers(int n) {
   // starting the loop from 1 as 1 is the first ugly number.
   int i = 1;

   // Ugly number counter
   int counter = 1;

   // checking whether the ith number is an ugly number or not.
   while (n > counter) {
      i++;

      // If the ith number is an ugly number then increment the counter
      if (isUglyNumber(i))
         counter++;
   }
   return i;
}

int main() {
   int n = 7;
   int answer = findUglyNumbers(n);
   cout << n << "th ugly number is: " << answer;

   return 0;
}

Java Code

public class Main {

	// a function that will divide the dividend by the maximum power of divisor and then return the dividend.
	static int maximumDivisible(int dividend, int divisor) {
		while (dividend % divisor == 0)
			dividend = dividend / divisor;

		return dividend;
	}

	// A function that weill check whether the number n is an ugly number or not.
	static int isUglyNumber(int n) {
		n = maximumDivisible(n, 2);
		n = maximumDivisible(n, 3);
		n = maximumDivisible(n, 5);

		if (n == 1)
			return 1;
		else
			return 0;
	}

	// a function tha that will find and return the nth ugly number.
	static int findUglyNumbers(int n) {
		// starting the loop from 1 as 1 is the first ugly number.
		int i = 1;

		// Ugly number counter
		int counter = 1;

		// checking whether the ith number is an ugly number or not.
		while (n > counter) {
			i++;

			// If the ith number is an ugly number then increment the counter
			if (isUglyNumber(i) == 1)
				counter++;
		}
		return i;
	}

	public static void main(String args[]) {
		int n = 7;
		int answer = findUglyNumbers(n);
		System.out.println(n + "th ugly number is: " + answer);
	}
}

Python Code

"""
a function that will divide the dividend by the maximum power of the divisor and then return the dividend.
"""
def maximumDivisible(dividend, divisor):
    while dividend % divisor == 0:
        dividend = dividend / divisor
    return dividend


"""
A function that will check whether the number n is an ugly number or not.
"""
def isUglyNumber(n):
    n = maximumDivisible(n, 2)
    n = maximumDivisible(n, 3)
    n = maximumDivisible(n, 5)

    if n == 1:
        return 1
    else:
        return 0


"""
a function that will find and return the nth ugly number.
"""
def findUglyNumbers(n):
    # starting the loop from 1 as 1 is the first ugly number.
    i = 1

    # Ugly number counter
    counter = 1

    # checking whether the ith number is ugly or not.
    while n > counter:
        i += 1

        # If the ith number is an ugly number, then increment the counter
        if isUglyNumber(i):
            counter += 1
    return i


n = 7
answer = findUglyNumbers(n)
print(str(n) + "th ugly number is:" + str(answer))

Output

7th ugly number is: 8

The above-discussed algorithm checks every number starting from 0, so this is a very time inefficient algorithm. For each number, we need to calculate the maximum divisible power of 2 or 3, or 5, and then check whether the calculated number is an ugly number or not.

Time Complexity

The time complexity for finding the nth ugly number using the brute force approach comes out to be O(n log n) because the complexity of the maximumDivisible function is O(log n).

Space Complexity

Since we are not using any extra space rather than some variables, the space complexity for finding the nth ugly number using the brute force approach comes out to be O(1).

Approach 2 – Dynamic Programming

A better approach to finding the nth ugly number can be using dynamic programming. Let us learn how.

Note: Dynamic Programming is an optimization algorithm that can be used to optimize recursion problems. Dynamic programming is used in scenarios where there are repeated recursive calls for the same input. Since there are repeated calls, we store the results for some recursive calls and use them to obtain results for larger problem.

As we know that the sequence of the ugly number is: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, … Apart from this, we also know that every number of the series can be divided by 2, 3, and 5 only. So, the above sequence can be rewritten in the form:

  • 1×2, 2×2, 3×2, 4×2, 5×2, …
  • 1×3, 2×3, 3×3, 4×3, 5×3, …
  • 1×5, 2×5, 3×5, 4×5, 5×5, …

So, we can conclude that the above sequence of the ugly numbers can be written in the form of an ugly number sequence multiplied by 2, 3, and 5. In this way, we can generate the arrays of the smaller ugly numbers sequence and then simply merge these sequences.

Refer to the next sub-section for the algorithm.

Algorithm

  • Create a function namely findUglyNumbers() that takes an input number n.
  1. Declare a dp array that will store the n ugly numbers.
  2. As we know that the first ugly number is 1 so initialize the first ugly number in the dp array as: dp[0] = 1.
  3. Now, initialize three variables to point to the first element of the array numbers (dp array) as:
    • i2 = i3 = i5 = 0 (Since, 2,3, and 5 are the prime factors of ugly numbers so we have decided the names according to that).
  4. Initialize the next three choices of the ugly numbers as they can easily be obtained by multiplying the number dp[0] with 2, 3, and 5.
    • nextMultipleOf2 = dp[i2] * 2;
    • nextMultipleOf3 = dp[i3] * 3;
    • nextMultipleOf5 = dp[i5] * 5;
  5. Now, we will run a loop and find the n possible ugly numbers. Inside the loop we will perform certain steps:
    • We will find the next ugly number as the next ugly number would be simply the minimum of the next multiples of 2, 3, and 5.
    • We will now insert the next ugly number at the i-th position in the dp array as it is the i-th ugly number.
    • Now, we will perform simple checks to update the next multiples.
  6. Finally, we will return the nextUglyNumber as result.

Refer to the next sub-section for the code implementation in various programming languages.

Code Implementation

Let us see the code for the above-discussed algorithm.

C++ Code

#include <bits/stdc++.h>
using namespace std;

// a function tha that will find and return the nth ugly number.
int findUglyNumbers(int n) {
   // To store ugly numbers
   int dp[n];

   int i2 = 0, i3 = 0, i5 = 0;

   int nextMultipleOf2 = 2;
   int nextMultipleOf3 = 3;
   int nextMultipleOf5 = 5;

   int nextUglyNumber = 1;

   // array that will contain ugly numbers.
   dp[0] = 1; 
   for (int i = 1; i < n; i++) {
      // calculating the next ugly number as it would be simply the minimum of the next multiples of 2, 3, and 5.
      nextUglyNumber = min(
          nextMultipleOf2,
          min(nextMultipleOf3, nextMultipleOf5));
      /*
      We will now insert the next ugly number at the ith position in the dp array as it is the ith ugly number.
      */
      dp[i] = nextUglyNumber;

      /*
      if the nextUglyNumber is a nextMultipleOf2 then increment the i2 counter and insert it in the dp array.
      */
      if (nextUglyNumber == nextMultipleOf2) {
         i2 = i2 + 1;
         nextMultipleOf2 = dp[i2] * 2;
      }
      /*
      if the nextUglyNumber is a nextMultipleOf3 then increment the i3 counter and insert it in the dp array.
      */
      if (nextUglyNumber == nextMultipleOf3) {
         i3 = i3 + 1;
         nextMultipleOf3 = dp[i3] * 3;
      }

      /*
      if the nextUglyNumber is a nextMultipleOf5 then increment the i5 counter and insert it in the dp array.
      */
      if (nextUglyNumber == nextMultipleOf5) {
         i5 = i5 + 1;
         nextMultipleOf5 = dp[i5] * 5;
      }
   }

   // return the nextUglyNumber as result.
   return nextUglyNumber;
}

int main() {
   int n = 7;
   int answer = findUglyNumbers(n);
   cout << n << "th ugly number is: " << answer;

   return 0;
}

Java Code

public class Main {

	// a function tha that will find and return the nth ugly number.
	static int findUglyNumbers(int n) {
		// To store ugly numbers
		int dp[] = new int[n];

		int i2 = 0, i3 = 0, i5 = 0;

		int nextMultipleOf2 = 2;
		int nextMultipleOf3 = 3;
		int nextMultipleOf5 = 5;

		int nextUglyNumber = 1;

		// array that will contain ugly numbers.
		dp[0] = 1;
		for (int i = 1; i < n; i++) {
			// calculating the next ugly number as it would be simply the minimum of the
			// next multiples of 2, 3, and 5.
			nextUglyNumber = Math.min(
					nextMultipleOf2,
					Math.min(nextMultipleOf3, nextMultipleOf5));
			/*
			We will now insert the next ugly number at the ith position in the dp array as it is the ith ugly number.
			*/
			dp[i] = nextUglyNumber;

			/*
			if the nextUglyNumber is a nextMultipleOf2 then increment the i2 counter and insert it in the dp array.
			*/
			if (nextUglyNumber == nextMultipleOf2) {
				i2 = i2 + 1;
				nextMultipleOf2 = dp[i2] * 2;
			}
			/*
			if the nextUglyNumber is a nextMultipleOf3 then increment the i3 counter and insert it in the dp array.
			*/
			if (nextUglyNumber == nextMultipleOf3) {
				i3 = i3 + 1;
				nextMultipleOf3 = dp[i3] * 3;
			}

			/*
			if the nextUglyNumber is a nextMultipleOf5 then increment the i5 counter and insert it in the dp array.
			*/
			if (nextUglyNumber == nextMultipleOf5) {
				i5 = i5 + 1;
				nextMultipleOf5 = dp[i5] * 5;
			}
		}

		// return the nextUglyNumber as result.
		return nextUglyNumber;
	}

	public static void main(String args[]) {
		int n = 7;
		int answer = findUglyNumbers(n);
		System.out.println(n + "th ugly number is: " + answer);
	}
}

Python Code

"""
a function that will find and return the nth ugly number.
"""
def findUglyNumbers(n):
    # To store ugly numbers
    dp = [0] * n

    # inserting the first ugly number.
    dp[0] = 1

    i2 = i3 = i5 = 0

   
    nextMultipleOf2 = 2
    nextMultipleOf3 = 3
    nextMultipleOf5 = 5


    for i in range(1, n):
        """
        calculating the next ugly number as it would be simply the minimum of the next multiples of 2, 3, and 5.

        We will insert the next ugly number at the ith position in the dp array as it is the ith ugly number.
        """
        dp[i] = min(nextMultipleOf2,
                    nextMultipleOf3,
                    nextMultipleOf5)

        # if the nextUglyNumber is a nextMultipleOf2 then increment the i2 counter and insert it in the dp array.
        if dp[i] == nextMultipleOf2:
            i2 += 1
            nextMultipleOf2 = dp[i2] * 2

        # if the nextUglyNumber is a nextMultipleOf3 then increment the i3 counter and insert it in the dp array.
        if dp[i] == nextMultipleOf3:
            i3 += 1
            nextMultipleOf3 = dp[i3] * 3

        # if the nextUglyNumber is a nextMultipleOf5 then increment the i5 counter and insert it in the dp array.
        if dp[i] == nextMultipleOf5:
            i5 += 1
            nextMultipleOf5 = dp[i5] * 5

    # return the dp[-1] as result.
    return dp[-1]


n = 7
answer = findUglyNumbers(n)
print(str(n) + "th ugly number is:" + str(answer))

Output

7th ugly number is: 8

Time Complexity

The time complexity for finding the nth ugly number using the dynamic programming approach comes out to be O(n), where n is the provided input number.

Space Complexity

Since we are using an extra space of dp array, the space complexity for finding the nth ugly number using the dynamic programming approach comes out to be O(n).

Approach 3 – Using SET Data Structure in C++, Javascript, and TreeSet in JAVA

Another approach to finding the nth ugly number can be using a set data structure.

Note: A set is a collection of unordered values or items. The set data structure has similar properties to the set in mathematics.

In this approach, we will first generate the three ugly numbers and then store the minimum of the three generated ugly numbers that resemble the ith ugly number. This ith ugly number will be stored at the first position in the set data structure.

Refer to the next sub-section for the algorithm.

Algorithm

  • Create a function namely findUglyNumbers() that takes an input number n.
  1. Define the base case that the number lies between 1 to 5 then return the number itself as the nth ugly number.
  2. Insert the number 11 as the first ugly number in the set.
  3. Find the beginning element of the set and add the next multiples of 2, 3, and 5 (multiplied with the first element of the set) into the set.
    • Example: if the set’s first element = x, then insert the following number into the set:
      • x * 2
      • x * 3
      • x * 5
  4. Sort the set and decrement and repeat the above steps by decreasing the value of n.
  5. At last, return the first element of the set as the nth ugly number.

Refer to the next sub-section for the code implementation in various programming languages.

Code Implementation

Let us see the code for the above-discussed algorithm.

C++ Code

#include <bits/stdc++.h>
using namespace std;

// a function tha that will find and return the nth ugly number.
int findUglyNumbers(int n) {
   // defining the base case.
   if (n == 1 or n == 2 or n == 3 or n == 4 or n == 5)
      return n;

   // declaring a set data structure.
   set<int> s;

   // adding 1 as the first ugly number into the set.
   s.insert(1);
   
   // since the first number is inserted, we decrement the value of n
   n--;

   while (n) {
      // an iterator for the set data structure..
      auto it = s.begin();

      // getting the first element of the set.
      int topElement = *it;

      // removing the ith element from the set.
      s.erase(it);

      // inserting all the three multiples of top element.
      s.insert(topElement * 2);
      s.insert(topElement * 3);
      s.insert(topElement * 5);

      // decrementing the value of n.
      n--;
   }

   // Returning the top element of the set.
   return *s.begin();
}

int main() {
   int n = 7;
   int answer = findUglyNumbers(n);
   cout << n << "th ugly number is: " << answer;

   return 0;
}

Java Code

import java.util.*;

public class Main {

	// a function that will find and return the nth ugly number.
	static int findUglyNumbers(int n) {

		// declaring a tree set data structure.
		TreeSet<Integer> t = new TreeSet<>();

		// adding 1 as the first ugly number into the set.
		t.add(1);
		int i = 1;

		// since the first number is inserted, we increment the value of i as i is acting like a counter.
		while (i < n) {

			// getting the first element of the set and removing tit from the set.
			int topElement = t.pollFirst();

			// inserting all the three multiples of top element.
			t.add(topElement * 2);
			t.add(topElement * 3);
			t.add(topElement * 5);

			// incrementing the value of n.
			i++;
		}
		// Returning the top element of the set.
		return t.pollFirst();
	}

	public static void main(String args[]) {
		int n = 7;
		int answer = findUglyNumbers(n);
		System.out.println(n + "th ugly number is: " + answer);
	}
}

Python Code

"""
a function that will find and return the nth ugly number.
"""
def findUglyNumbers(n):
    # defining the base case.
    if (n == 1 or n == 2 or n == 3 or n == 4 or n == 5):
        return n

    # declaring a set data structure.
    # adding 1 as the first ugly number into the set.
    s = [1]

    # since the first number is inserted, we decrement the value of n
    n -= 1

    while (n):
        # an iterator for the set data structure.
        it = s[0]

        #  getting the first element of the set.
        topElement = it

        # removing the ith element from the set.
        s = s[1:]
        s = set(s)

        # inserting all the three multiples of top element.
        s.add(topElement * 2)
        s.add(topElement * 3)
        s.add(topElement * 5)

        # converting the set into a list.
        s = list(s)

        # sorting the set converted into the list.
        s.sort()

        # decrementing the value of n.
        n -= 1
        
    # Returning the top element of the set.
    return s[0]


n = 7
answer = findUglyNumbers(n)
print(str(n) + "th ugly number is:" + str(answer))

Output

7th ugly number is: 8

In this approach to finding the nth ugly number, we are using a set data structure to store the result and we are traversing the numbers from 1 to n.

Time Complexity

The time complexity for finding the nth ugly number using the set data structure approach comes out to be roughly O(n log n).

Space Complexity

Since we are using an extra space of set data structure, the space complexity for finding the n-th ugly number using the set data structure approach comes out to be O(n), where n is the size of the set.

Approach 4 – Using Binary Search

Another efficient approach to finding the nth ugly number can be using the Binary Search technique.

Note: Binary Search is a searching technique that works on sorted objects. Instead of comparing each element with the required element, the binary search algorithm repeatedly divides the sorted objects into smaller sub-objects and then searches the required element in the sub-object.

We can use the range of ugly numbers i.e. from $1$ to $21474836647$. We can repeatedly divide this range to get our desired result.

Refer to the next sub-section for the algorithm.

Algorithm

  • Create a function namely findUglyNumbers() that takes an input number n.
  1. Define the lower and upper bound of the number i.e. 1 to 21474836647.
  2. Start searching in the specified range.
  3. Find the mid value of the range, and then check for the mid value. If the mid value is larger then shift the higher range to mid (low is the same and high becomes mid) else shift the lower range to mid+1 (high is the same and low becomes mid+1).

Refer to the next sub-section for the code implementation in various programming languages.

Code Implementation

Let us see the code for the above-discussed algorithm.

C++ Code

#include <bits/stdc++.h>
using namespace std;

// a function tha that will find and return the nth ugly number.
int findUglyNumbers(int n) {
   int powers[40] = {1};

   // storing the powers
   for (int i = 1; i <= 30; ++i)
      powers[i] = powers[i - 1] * 2;

   // Initializing the low and high range.
   int start = 1, end = 2147483647;

   int answer = -1;

   while (start <= end) {
      // finding the mid value
      int mid = start + ((end - start) / 2);

      // counter stores total numbers of ugl numbers
      int counter = 0;

      for (long long i = 1; i <= mid; i *= 5) {
         // checking the possible powers of i that are less than and equal to mid.
         for (long long j = 1; j * i <= mid; j *= 3) {
            // changing the upper bound
            counter += upper_bound(powers, powers + 31,
                                   mid / (i * j)) -
                       powers;
         }
      }

      /*
      If the total number of ugly number
      less than equal to mid then updating the start value
      */
      if (counter < n)
         start = mid + 1;

      // else updating the end value
      else
         end = mid - 1, answer = mid;
   }

   return answer;
}

int main() {
   int n = 7;
   int answer = findUglyNumbers(n);
   cout << n << "th ugly number is: " << answer;

   return 0;
}

Java Code

import java.util.*;

public class Main {

	// a function that will calculate the upper bound for the range low and high according to the provided number
	static int upperBound(int[] a, int low,
			int high, int number) {
		while (low < high) {
			int middle = low + (high - low) / 2;

			if (a[middle] > number)
				high = middle;
			else
				low = middle + 1;
		}
		return low;
	}

	// a function tha that will find and return the nth ugly number.
	static int findUglyNumbers(int n) {
		int power[] = new int[40];
		Arrays.fill(power, 1);

		// storing the powers
		for (int i = 1; i <= 30; ++i)
			power[i] = power[i - 1] * 2;

		// Initializing the low and high range.
		int low = 1, high = 2147483647;

		int answer = -1;

		while (low <= high) {

			// finding the mid value
			int mid = low + ((high - low) / 2);

			// counter stores total numbers of ugl numbers
			int count = 0;

			for (long i = 1; i <= mid; i *= 5)
			// checking the possible powers of i that are less than and equal to mid.
			{
				for (long j = 1; j * i <= mid; j *= 3)
				{
					// changing the upper bound
					count += upperBound(power, 0, 31,
							(int) (mid / (i * j)));
				}
			}

			/*
			If the total number of ugly number
			less than equal to mid then updating the start value
			*/
			if (count < n)
				low = mid + 1;

			// else updating the end value
			else {
				high = mid - 1;
				answer = mid;
			}
		}

		return answer;
	}

	public static void main(String args[]) {
		int n = 7;
		int answer = findUglyNumbers(n);
		System.out.println(n + "th ugly number is: " + answer);
	}
}

Python Code

"""
a function that will calculate the upper bound for the range low and high according to the provided number
"""
def upperBound(a, low, high, number):
    while(low < high):
        middle = low + (high - low)//2
        if(a[middle] > number):
            high = middle
        else:
            low = middle + 1

    return low


"""
a function that will find and return the nth ugly number.
"""
def findUglyNumbers(n):
    power = [1] * 40

    # storing the powers
    for i in range(1, 31):
        power[i] = power[i - 1] * 2

    # Initializing the low and high range.
    low = 1
    high = 2147483647

    answer = -1

    while (low <= high):
        # finding the mid value
        mid = low + ((high - low) // 2)

        # counter stores total numbers of ugly numbers
        count = 0

        # Iterate from 1 to mid
        i = 1
        while(i <= mid):
            # checking the possible powers of i that are less than and equal to mid.
            j = 1
            while(j * i <= mid):
                # changing the upper bound
                count += upperBound(power, 0,  31, mid // (i * j))
                j *= 3

            i *= 5

        """
        If the total number of ugly number
		less than equal to mid then updating the start value.
        """
        if (count < n):
            low = mid + 1

        #  else updating the end value
        else:
            high = mid - 1
            answer = mid
    return answer


n = 7
answer = findUglyNumbers(n)
print(str(n) + "th ugly number is:" + str(answer))

Output

7th ugly number is: 8

We are using an iterative binary search and dividing the range of the ugly numbers into halves in each iteration. We are not using any extra space for performing the binary search.

Time Complexity

The time complexity for finding the nth ugly number using the binary search approach comes out to be O(log n).

Space Complexity

Since we are not using any extra space apart from some variables, the space complexity for finding the nth ugly number using the binary search approach comes out to be O(1).

Conclusion

  • An ugly number is a number whose prime factors are 2, 3, or 5 only.
  • The brute force approach to finding the n-th ugly number can be running a loop and maintaining a counter that will increase once a number is encountered as an ugly number.
  • The time complexity for finding the n-th ugly number using the brute force approach comes out to be O(n log n), and the space complexity comes out to be O(1) as we are not using any extra space.
  • Another approach to finding the n-th ugly number can be using dynamic programming. We can store the precalculated results and use them to calculate the next results.
  • The time complexity for finding the n-th ugly number using the dynamic programming approach comes out to be O(n), and the space complexity comes out to be O(n) as we use an extra dp array.
  • Another approach to finding the n-th ugly number can be traversing the numbers from 1 to n and using a set data structure to store the results.
  • The time complexity for finding the n-th ugly number using the set data structure approach comes out to be O(n log n), and the space complexity comes out to be O(1) as we are not using any extra space.
  • Another approach to finding the n-th ugly number can be using the iterative binary search and dividing the range of the ugly numbers into halves in each iteration.
  • The time complexity for finding the n-th ugly number using the binary search approach comes out to be O(log n), and the space complexity comes out to be O(1) as we are not using any extra space.

Author

Latest articles

Largest Number Formed from an Array

Sindhuja Gudala

Fundamentals of Enhanced Interior Gateway Routing Protocol

Trapti Gupta

What is Network Hub?

Akshay Mishra