Ugly Numbers — DP approach

ugly numbers wikipedia
first 100 ugly numbers
ugly numbers leetcode
super ugly numbers
bad ugly numbers codeforces
ugly numbers ii leetcode
ugly numbers 3
263. ugly number

Question: Ugly numbers are numbers whose only prime factors are 2, 3 or 5. The sequence 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, … shows the first 11 ugly numbers. By convention, 1 is included.

Given a number n, the task is to find n’th Ugly number. (https://www.geeksforgeeks.org/ugly-numbers/)

Answer: The Dynamic Programming approach in the above link

Psuedocode:

1 Declare an array for ugly numbers:  ugly[n]
2 Initialize first ugly no:  ugly[0] = 1
3 Initialize three array index variables i2, i3, i5 to point to 
   1st element of the ugly array: 
        i2 = i3 = i5 =0; 
4 Initialize 3 choices for the next ugly no:
         next_mulitple_of_2 = ugly[i2]*2;
         next_mulitple_of_3 = ugly[i3]*3
         next_mulitple_of_5 = ugly[i5]*5;
5 Now go in a loop to fill all ugly numbers till 150:
For (i = 1; i < 150; i++ ) 
{
    /* These small steps are not optimized for good 
      readability. Will optimize them in C program */
    next_ugly_no  = Min(next_mulitple_of_2,
                        next_mulitple_of_3,
                        next_mulitple_of_5); 

    ugly[i] =  next_ugly_no       

    if (next_ugly_no  == next_mulitple_of_2) 
    {             
        i2 = i2 + 1;        
        next_mulitple_of_2 = ugly[i2]*2;
    } 
    if (next_ugly_no  == next_mulitple_of_3) 
    {             
        i3 = i3 + 1;        
        next_mulitple_of_3 = ugly[i3]*3;
     }            
     if (next_ugly_no  == next_mulitple_of_5)
     {    
        i5 = i5 + 1;        
        next_mulitple_of_5 = ugly[i5]*5;
     } 

}/* end of for loop */ 
6.return next_ugly_no

Doubts:

I don't understand the DP approach in this case.

  1. What are the subproblems?
  2. What is the recursion in this case?
  3. How are the subproblems overlapping?
  4. Why do we keep track of current ugly number? Why not just go through the multiples of 2,3,5 and each point keep taking minimum.

    Like 2,3,5. Then 4,3,5, Then 4,6,5..keeps incrementing the multiples of each.

Related Question: nth ugly number ( I weent through the answers but I was confused in the above questions I mentioned.)

  1. subproblems: find all numbers that are multiples of 2, of 3, of 5
  2. recursion: the use of previous ugly numbers to calculate future ugly numbers. the dynamic programming solution short circuits the need for the recursion by use of storage.
  3. overlapping: the output needs to be in numeric order so its not clear which subproblem will generate the next in sequence.
  4. why keep track: without reusing the previous ugly numbers you would only get the exponent results 2^n, 3^n, 5^n

further optimization: space reduction could be achieved by pruning the ugly array to unset any values which are < min(i2,i3,i5) as they will never be needed again.

Ugly Numbers, Ugly numbers are those number whose prime factors are 2, 3 or 5. From 1 to 15, there are 11 ugly numbers 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15. The numbers 7, 11, 13 are not ugly because they are prime. The number 14 is not ugly because in its prime factor the 7 will come. Ugly numbers are those number whose prime factors are 2, 3 or 5. From 1 to 15, there are 11 ugly numbers 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15. The numbers 7, 11, 13 are

Ugly Number II, Ugly numbers are positive numbers whose prime factors only include 2, 3, 5 . Example: Input: n = 10 Output: 12 Explanation: 1, 2, 3, 4, 5, 6, 8, 9� Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. Example 1: Input: 6 Output: true Explanation: 6 = 2 × 3. Example 2: Input: 8 Output: true Explanation: 8 = 2 × 2 × 2 Example 3: Input: 14 Output: false Explanation: 14 is not ugly since it includes another prime factor 7. Note: 1 is typically treated as an ugly number.

t = int(input())

# function to get all the numbers with prime factors within a given range

def prime(n):
    global l
    a = []
    i = 1
    while (i <= n):
        k = 0
        if (n % i == 0):
            j = 1
            while (j <= i):
                if (i % j == 0):
                    k = k + 1
                j = j + 1
            if (k == 2):
                a.append(i)
        i = i + 1
    check(a)

#function to filter all non-ugly numbers

def check(a):
    if (all(x in l for x in a)):
        everything.append(n)

# main code

while t >0:
    h = int(input())
    l = [2, 3, 5]
    everything = []
    for n in range(1, h**2):
        prime(n)
    print(everything[h - 1])
    t-=1

Ugly Number, Ugly numbers are positive numbers whose prime factors only include 2, 3, 5 . Example 1: Input: 6 Output: true Explanation: 6 = 2 � 3. Example 2: Input: 8 Output :� Write a program to find the n-th ugly number. Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12

Ugly Number (Dynamic Programming), Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. Note that 1 is typically treated as an ugly number. Example: 10th ugly number is 12, because first 10 ugly numbers are 1, 2, 3, 4, 5, 6, 8, 9, 10, 12. The numbers 7, 11, 13 are not ugly because they are prime. The number 14 is not ugly because in its prime factor the 7 will come. So suppose we want to check the 10th ugly number. The value will be 12. Let us see the following algorithm to get an idea − Algorithm. getUglyNumbers(n) Input − The number of terms. Output − Find nth Ugly numbers.

Ugly Number Problems on LeetCode. The problems on leetcode are , Ugly numbers are positive numbers whose prime factors only include 2, 3, 5 . For example, 6, 8 are ugly while 14 is not ugly since it includes� So after n ugly numbers are found we have at most 2n + 1 elements in the queue. Extracting an element can be done in logarithmic time. We extract more numbers than just the ugly numbers but at most n ugly numbers plus 2n - 1 other numbers (those that could have been in the sieve after n-1 steps).

UGLY Numbers Dynamic Programming | LeetCode 264, Correction: At 2:22 while listing Ugly numbers I added 14 also in list. 14 should not be there Duration: 21:10 Posted: Apr 30, 2019 Ugly numbers are numbers whose only prime factors are 2, 3 or 5. The sequence 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, … shows the first 11 ugly numbers.

Comments
  • You need to post the question in that article here. When that link goes dead, this whole question and the answers become useless to everyone.
  • @Rob included, thanks for suggestion. Included answer as well. Let me know if there is still some problem.
  • there are two options for keeping track in an ordered sequence - either track future or track past. the posted solution tracks past. to your point, you could calculate 3 future ugly numbers for each ugly number discovered but then you would have to store those future numbers and remove duplicates as you go forward. future storage in this case appears more complex than past storage.
  • ideone.com/q3fma is apparently the currently best and ideal solution as it is able to also estimate the approximate range of the Nth number and not calculate all the way up there.
  • Can you explain the recursion in greater detail, it is tough to make out from your answer right now.
  • recursion is the concept of calling the same function to get the answer for a sub problem. so there are two ways to do this: one is to spend time running an algorithm or two is to do a lookup. so the lookup phase is the recursion