Ugly Numbers — DP approach

Question

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.)

Answer 1

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.

Answer 2

This is how I would formulate the problem in terms of sub-problems:

The i-th Ugly Number is obtained by multiplying another Ugly Number (strictly smaller than the i-th) by 2, 3 or 5. The first Ugly Number is 1.

Therefore:

// dp[i] ... the i-th ugly number
dp[1] = 1;
i2 = i3 = i5 = 1;
for i in 2 .. n:
  dp[i] = min(2*dp[i2], 3*dp[i3], 5*dp[i5]);
  // where: 1 <= i2, i3, i5 < i

  i2 = update(dp[i], i2, 2);
  i3 = update(dp[i], i3, 3);
  i5 = update(dp[i], i5, 5);
return dp[n];

update(ref, j, k):
  if (ref == k * dp[j]):
    return j + 1;
  return j;

Here is how the proposed algorithm runs:

The sub-problems do overlap. Take for example dp[6] and dp[4]. Both are produced by making use of dp[2]:

dp[4] = min(2*dp[2], 3*dp[2], 5*dp[1]);
dp[6] = min(2*dp[3], 3*dp[2], 5*dp[2]);

The solution has to be built using the bottom-up approach (refer to the "Bottom-up approach" bullet under the Computer programming section of the Dynamic Programming) in order to establish the indexing of Ugly Numbers.

GeeksforGeeks implementation notes

• do not make heap allocations; it's too slow

  • the best way is to allocate the dp array once (make sure it is big enough) and re-use it in all the test cases

• use of subroutines

  • min(min(a, b), c) is okay, min({a, b, c}) (C++) will exceed the time limit

  • update() logic has to be integrated into the main algorithm or you will exceed the time limit

• input is large (10k lines); consider using some sort of buffered read utilities

---

There is indeed a simpler but slower (O (n log n)) solution that you hinted at and is pointed out in the answers to this question. This is how it looks in Java:

TreeSet<Long> multiples = new TreeSet<Long>();

long first = 1;
for (int i = 1; i < n; i++) {
    multiples.add(first * 2);
    multiples.add(first * 3);
    multiples.add(first * 5);
    first = multiples.pollFirst();
}
return first;

Note

Such a solution is not likely to pass the set Time Limit at GeeksforGeeks.

Given the t test cases, each designated by the ordinal of the Ugly Number to compute (n), we can express the time complexities of both solutions:

• t * n - for the linear solution

• t * n * log2(n) - for the "TreeSet" solution

Dividing the two yields how many times slower the "TreeSet" solution is relative to the linear one:

t * n * log2(n)
--------------- = log2(n)
t * n

The linear solution runs at about 600 to 800 milliseconds; 700 on average.

If we multiply that with log2(10000) (.7s * log2(10000) = 6.98s), we get a run-time approximation for the "TreeSet" solution which is well above the set Time Limit:

Expected Time Limit < 1.2736sec

Answer 3

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