Posted on by Kalkicode
Code Dynamic Programming

Print Ugly Numbers

The given problem is to print the first N ugly numbers using dynamic programming. Ugly numbers are positive integers whose only prime factors are 2, 3, or 5. The task is to find and print the Nth ugly number and all the preceding ones in ascending order.

Problem Statement

The goal is to write a program that prints the first N ugly numbers using dynamic programming. An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5. The program should take an integer N as input and print the N ugly numbers in ascending order.

Example

Let's take N = 10 as an example to demonstrate how the program works:

  1. Start with the first ugly number, which is 1.
  2. The next ugly number is the minimum among the multiples of 2, 3, and 5. In this case, it's 2.
  3. The next ugly number is the minimum among the multiples of 2, 3, and 5, excluding the numbers already found. In this case, it's 3.
  4. The next ugly number is the minimum among the multiples of 2, 3, and 5, excluding the numbers already found. In this case, it's 4 (multiple of 2).
  5. Continuing this process, we find the next ugly numbers: 5, 6 (multiple of 2 and 3), 8 (multiple of 2), 9 (multiple of 3), and 10 (multiple of 2 and 5).

The first 10 ugly numbers are: 1, 2, 3, 4, 5, 6, 8, 9, 10.

Standard Pseudocode

function find_min(a, b):
    if a > b:
        return b
    return a

function ugly_number(n):
    no_2 = 2, no_3 = 3, no_5 = 5
    two = 0, three = 0, five = 0
    collection = array of size n
    collection[0] = 1

    for i from 1 to n - 1:
        collection[i] = find_min(no_2, find_min(no_3, no_5))
        if no_2 == collection[i]:
            two++
            no_2 = collection[two] * 2
        if no_3 == collection[i]:
            three++
            no_3 = collection[three] * 3
        if no_5 == collection[i]:
            five++
            no_5 = collection[five] * 5

    for i from 0 to n - 1:
        print collection[i]

Algorithm Explanation

  1. We start with the first ugly number, which is 1. We also initialize three variables no_2, no_3, and no_5, which represent the multiples of 2, 3, and 5, respectively.
  2. We also initialize three variables two, three, and five, which represent the indices of the next ugly number to be multiplied by 2, 3, and 5, respectively.
  3. We create an array collection of size N to store the N ugly numbers, and we set the first element of this array to 1, as 1 is the first ugly number.
  4. Now, we loop from i = 1 to i = n - 1 (n is the given input N) to find the remaining N - 1 ugly numbers.
  5. At each step, we find the minimum among the three candidates (no_2, no_3, and no_5) and store it in the collection array at index i.
  6. We then check which candidate is equal to the ugly number we just found and update the respective multiple and increment the corresponding index variable (two, three, or five).
  7. After the loop, the collection array contains the first N ugly numbers.
  8. Finally, we loop through the collection array and print the N ugly numbers in ascending order.

Note that 1 is typically treated as an ugly number. Here given code implementation process.

Code Solution

// C Program
// Print Ugly Numbers
// By dynamic programming
#include <stdio.h>

// Returns minimum value of two numbers
int find_min(int a, int b)
{
    if (a > b)
    {
        //when b is small
        return b;
    }
    //when a is small
    return a;
}
void ugly_number(int n)
{
    // initial values 
    int no_2 = 2, no_3 = 3, no_5 = 5;
    // initial values of three location
    int two = 0, three = 0, five = 0;
    // Use to store N ugly numbers
    int collection[n];
    // Set first ugly number
    collection[0] = 1;
    for (int i = 1; i < n; ++i)
    {
        // Assign that minimum value of three numbers
        collection[i] = find_min(no_2, find_min(no_3, no_5));
        if (no_2 == collection[i])
        {
            two++;
            no_2 = collection[two] *2;
        }
        if (no_3 == collection[i])
        {
            three++;
            no_3 = collection[three] *3;
        }
        if (no_5 == collection[i])
        {
            five++;
            no_5 = collection[five] *5;
        }
    }
    // Display ugly number
    for (int i = 0; i < n; ++i)
    {
        printf("%d  ", collection[i]);
    }
}
int main()
{
    int n = 20;
    ugly_number(n);
    return 0;
}

Output

1  2  3  4  5  6  8  9  10  12  15  16  18  20  24  25  27  30  32  36
// Java Program
// Print Ugly Numbers
// By dynamic programming
public class PrintUglyNumber
{
    // Returns minimum value of two numbers
    public int findMin(int a, int b)
    {
        if (a > b)
        {
            // When b is small
            return b;
        }
        // When a is small
        return a;
    }
    public void uglyNumber(int n)
    {
        // initial values 
        int no_2 = 2, no_3 = 3, no_5 = 5;
        // initial values of three location
        int two = 0, three = 0, five = 0;
        // Use to store N ugly numbers
        int[] collection = new int[n];
        // Set first ugly number
        collection[0] = 1;
        for (int i = 1; i < n; ++i)
        {
            // Assign that minimum value of three numbers
            collection[i] = findMin(no_2, findMin(no_3, no_5));
            if (no_2 == collection[i])
            {
                two++;
                no_2 = collection[two] * 2;
            }
            if (no_3 == collection[i])
            {
                three++;
                no_3 = collection[three] * 3;
            }
            if (no_5 == collection[i])
            {
                five++;
                no_5 = collection[five] * 5;
            }
        }
        //Display ugly number
        for (int i = 0; i < n; ++i)
        {
            System.out.print(" " + collection[i]);
        }
    }
    public static void main(String[] args)
    {
        PrintUglyNumber task = new PrintUglyNumber();
        // Test Case
        task.uglyNumber(20);
    }
}

Output

 1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36
package main
import "fmt"
// Go Program
// Print Ugly Numbers
// By dynamic programming
type PrintUglyNumber struct {}
func getPrintUglyNumber() * PrintUglyNumber {
    var me *PrintUglyNumber = &PrintUglyNumber {}
    return me
}
// Returns minimum value of two numbers
func(this PrintUglyNumber) findMin(a, b int) int {
    if a > b {
        // When b is small
        return b
    }
    // When a is small
    return a
}
func(this PrintUglyNumber) uglyNumber(n int) {
    // initial values 
    var no_2 int = 2
    var no_3 int = 3
    var no_5 int = 5
    // initial values of three location
    var two int = 0
    var three int = 0
    var five int = 0
    // Use to store N ugly numbers
    var collection = make([] int, n)
    // Set first ugly number
    collection[0] = 1
    for i := 1 ; i < n ; i++ {
        // Assign that minimum value of three numbers
        collection[i] = this.findMin(no_2, this.findMin(no_3, no_5))
        if no_2 == collection[i] {
            two++
            no_2 = collection[two] * 2
        }
        if no_3 == collection[i] {
            three++
            no_3 = collection[three] * 3
        }
        if no_5 == collection[i] {
            five++
            no_5 = collection[five] * 5
        }
    }
    //Display ugly number
    for i := 0 ; i < n ; i++ {
        fmt.Print(" ", collection[i])
    }
}
func main() {
    var task * PrintUglyNumber = getPrintUglyNumber()
    // Test Case
    task.uglyNumber(20)
}

Output

 1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36
// Include header file
#include <iostream>
using namespace std;
// C++ Program
// Print Ugly Numbers
// By dynamic programming
class PrintUglyNumber
{
    public:
        // Returns minimum value of two numbers
        int findMin(int a, int b)
        {
            if (a > b)
            {
                // When b is small
                return b;
            }
            // When a is small
            return a;
        }
    void uglyNumber(int n)
    {
        // initial values 
        int no_2 = 2;
        int no_3 = 3;
        int no_5 = 5;
        // initial values of three location
        int two = 0;
        int three = 0;
        int five = 0;
        // Use to store N ugly numbers
        int collection[n];
        // Set first ugly number
        collection[0] = 1;
        for (int i = 1; i < n; ++i)
        {
            // Assign that minimum value of three numbers
            collection[i] = this->findMin(no_2, 
                            this->findMin(no_3, no_5));
            if (no_2 == collection[i])
            {
                two++;
                no_2 = collection[two] *2;
            }
            if (no_3 == collection[i])
            {
                three++;
                no_3 = collection[three] *3;
            }
            if (no_5 == collection[i])
            {
                five++;
                no_5 = collection[five] *5;
            }
        }
        //Display ugly number
        for (int i = 0; i < n; ++i)
        {
            cout << " " << collection[i];
        }
    }
};
int main()
{
    PrintUglyNumber *task = new PrintUglyNumber();
    // Test Case
    task->uglyNumber(20);
    return 0;
}

Output

 1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36
// Include namespace system
using System;
// Csharp Program
// Print Ugly Numbers
// By dynamic programming
public class PrintUglyNumber
{
    // Returns minimum value of two numbers
    public int findMin(int a, int b)
    {
        if (a > b)
        {
            // When b is small
            return b;
        }
        // When a is small
        return a;
    }
    public void uglyNumber(int n)
    {
        // initial values 
        int no_2 = 2;
        int no_3 = 3;
        int no_5 = 5;
        // initial values of three location
        int two = 0;
        int three = 0;
        int five = 0;
        // Use to store N ugly numbers
        int[] collection = new int[n];
        // Set first ugly number
        collection[0] = 1;
        for (int i = 1; i < n; ++i)
        {
            // Assign that minimum value of three numbers
            collection[i] = this.findMin(no_2, this.findMin(no_3, no_5));
            if (no_2 == collection[i])
            {
                two++;
                no_2 = collection[two] * 2;
            }
            if (no_3 == collection[i])
            {
                three++;
                no_3 = collection[three] * 3;
            }
            if (no_5 == collection[i])
            {
                five++;
                no_5 = collection[five] * 5;
            }
        }
        //Display ugly number
        for (int i = 0; i < n; ++i)
        {
            Console.Write(" " + collection[i]);
        }
    }
    public static void Main(String[] args)
    {
        PrintUglyNumber task = new PrintUglyNumber();
        // Test Case
        task.uglyNumber(20);
    }
}

Output

 1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36
<?php
// Php Program
// Print Ugly Numbers
// By dynamic programming
class PrintUglyNumber
{
    // Returns minimum value of two numbers
    public  function findMin($a, $b)
    {
        if ($a > $b)
        {
            // When b is small
            return $b;
        }
        // When a is small
        return $a;
    }
    public  function uglyNumber($n)
    {
        // initial values 
        $no_2 = 2;
        $no_3 = 3;
        $no_5 = 5;
        // initial values of three location
        $two = 0;
        $three = 0;
        $five = 0;
        // Use to store N ugly numbers
        $collection = array_fill(0, $n, 0);
        // Set first ugly number
        $collection[0] = 1;
        for ($i = 1; $i < $n; ++$i)
        {
            // Assign that minimum value of three numbers
            $collection[$i] = $this->findMin(
              $no_2, $this->findMin($no_3, $no_5));
            if ($no_2 == $collection[$i])
            {
                $two++;
                $no_2 = $collection[$two] * 2;
            }
            if ($no_3 == $collection[$i])
            {
                $three++;
                $no_3 = $collection[$three] * 3;
            }
            if ($no_5 == $collection[$i])
            {
                $five++;
                $no_5 = $collection[$five] * 5;
            }
        }
        //Display ugly number
        for ($i = 0; $i < $n; ++$i)
        {
            echo(" ".strval($collection[$i]));
        }
    }
}

function main()
{
    $task = new PrintUglyNumber();
    // Test Case
    $task->uglyNumber(20);
}
main();

Output

 1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36
// Node JS Program
// Print Ugly Numbers
// By dynamic programming
class PrintUglyNumber
{
    // Returns minimum value of two numbers
    findMin(a, b)
    {
        if (a > b)
        {
            // When b is small
            return b;
        }
        // When a is small
        return a;
    }
    uglyNumber(n)
    {
        // initial values 
        var no_2 = 2;
        var no_3 = 3;
        var no_5 = 5;
        // initial values of three location
        var two = 0;
        var three = 0;
        var five = 0;
        // Use to store N ugly numbers
        var collection = Array(n).fill(0);
        // Set first ugly number
        collection[0] = 1;
        for (var i = 1; i < n; ++i)
        {
            // Assign that minimum value of three numbers
            collection[i] = this.findMin(no_2, 
                            this.findMin(no_3, no_5));
            if (no_2 == collection[i])
            {
                two++;
                no_2 = collection[two] * 2;
            }
            if (no_3 == collection[i])
            {
                three++;
                no_3 = collection[three] * 3;
            }
            if (no_5 == collection[i])
            {
                five++;
                no_5 = collection[five] * 5;
            }
        }
        //Display ugly number
        for (var i = 0; i < n; ++i)
        {
            process.stdout.write(" " + collection[i]);
        }
    }
}

function main()
{
    var task = new PrintUglyNumber();
    // Test Case
    task.uglyNumber(20);
}
main();

Output

 1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36
#  Python 3 Program
#  Print Ugly Numbers
#  By dynamic programming

class PrintUglyNumber :
    #  Returns minimum value of two numbers
    def findMin(self, a, b) :
        if (a > b) :
            #  When b is small
            return b
        
        #  When a is small
        return a
    
    def uglyNumber(self, n) :
        #  initial values 
        no_2 = 2
        no_3 = 3
        no_5 = 5
        #  initial values of three location
        two = 0
        three = 0
        five = 0
        #  Use to store N ugly numbers
        collection = [0] * (n)
        #  Set first ugly number
        collection[0] = 1
        i = 1
        while (i < n) :
            #  Assign that minimum value of three numbers
            collection[i] = self.findMin(no_2, self.findMin(no_3, no_5))
            if (no_2 == collection[i]) :
                two += 1
                no_2 = collection[two] * 2
            
            if (no_3 == collection[i]) :
                three += 1
                no_3 = collection[three] * 3
            
            if (no_5 == collection[i]) :
                five += 1
                no_5 = collection[five] * 5
            
            i += 1
        
        i = 0
        # Display ugly number
        while (i < n) :
            print(" ", collection[i], end = "")
            i += 1
        
    

def main() :
    task = PrintUglyNumber()
    #  Test Case
    task.uglyNumber(20)

if __name__ == "__main__": main()

Output

  1  2  3  4  5  6  8  9  10  12  15  16  18  20  24  25  27  30  32  36
#  Ruby Program
#  Print Ugly Numbers
#  By dynamic programming

class PrintUglyNumber 
    #  Returns minimum value of two numbers
    def findMin(a, b) 
        if (a > b) 
            #  When b is small
            return b
        end

        #  When a is small
        return a
    end

    def uglyNumber(n) 
        #  initial values 
        no_2 = 2
        no_3 = 3
        no_5 = 5
        #  initial values of three location
        two = 0
        three = 0
        five = 0
        #  Use to store N ugly numbers
        collection = Array.new(n) {0}
        #  Set first ugly number
        collection[0] = 1
        i = 1
        while (i < n) 
            #  Assign that minimum value of three numbers
            collection[i] = self.findMin(no_2, 
                            self.findMin(no_3, no_5))
            if (no_2 == collection[i]) 
                two += 1
                no_2 = collection[two] * 2
            end

            if (no_3 == collection[i]) 
                three += 1
                no_3 = collection[three] * 3
            end

            if (no_5 == collection[i]) 
                five += 1
                no_5 = collection[five] * 5
            end

            i += 1
        end

        i = 0
        # Display ugly number
        while (i < n) 
            print(" ", collection[i])
            i += 1
        end

    end

end

def main() 
    task = PrintUglyNumber.new()
    #  Test Case
    task.uglyNumber(20)
end

main()

Output

 1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36
// Scala Program
// Print Ugly Numbers
// By dynamic programming
class PrintUglyNumber()
{
    // Returns minimum value of two numbers
    def findMin(a: Int, b: Int): Int = {
        if (a > b)
        {
            // When b is small
            return b;
        }
        // When a is small
        return a;
    }
    def uglyNumber(n: Int): Unit = {
        // initial values 
        var no_2: Int = 2;
        var no_3: Int = 3;
        var no_5: Int = 5;
        // initial values of three location
        var two: Int = 0;
        var three: Int = 0;
        var five: Int = 0;
        // Use to store N ugly numbers
        var collection: Array[Int] = Array.fill[Int](n)(0);
        // Set first ugly number
        collection(0) = 1;
        var i: Int = 1;
        while (i < n)
        {
            // Assign that minimum value of three numbers
            collection(i) = findMin(no_2, findMin(no_3, no_5));
            if (no_2 == collection(i))
            {
                two += 1;
                no_2 = collection(two) * 2;
            }
            if (no_3 == collection(i))
            {
                three += 1;
                no_3 = collection(three) * 3;
            }
            if (no_5 == collection(i))
            {
                five += 1;
                no_5 = collection(five) * 5;
            }
            i += 1;
        }
        i = 0;
        //Display ugly number
        while (i < n)
        {
            print(" " + collection(i));
            i += 1;
        }
    }
}
object Main
{
    def main(args: Array[String]): Unit = {
        var task: PrintUglyNumber = new PrintUglyNumber();
        // Test Case
        task.uglyNumber(20);
    }
}

Output

 1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36
// Swift 4 Program
// Print Ugly Numbers
// By dynamic programming
class PrintUglyNumber
{
    // Returns minimum value of two numbers
    func findMin(_ a: Int, _ b: Int) -> Int
    {
        if (a > b)
        {
            // When b is small
            return b;
        }
        // When a is small
        return a;
    }
    func uglyNumber(_ n: Int)
    {
        // initial values 
        var no_2: Int = 2;
        var no_3: Int = 3;
        var no_5: Int = 5;
        // initial values of three location
        var two: Int = 0;
        var three: Int = 0;
        var five: Int = 0;
        // Use to store N ugly numbers
        var collection: [Int] = Array(repeating: 0, count: n);
        // Set first ugly number
        collection[0] = 1;
        var i: Int = 1;
        while (i < n)
        {
            // Assign that minimum value of three numbers
            collection[i] = self.findMin(no_2, self.findMin(no_3, no_5));
            if (no_2 == collection[i])
            {
                two += 1;
                no_2 = collection[two] * 2;
            }
            if (no_3 == collection[i])
            {
                three += 1;
                no_3 = collection[three] * 3;
            }
            if (no_5 == collection[i])
            {
                five += 1;
                no_5 = collection[five] * 5;
            }
            i += 1;
        }
        i = 0;
        //Display ugly number
        while (i < n)
        {
            print(" ", collection[i], terminator: "");
            i += 1;
        }
    }
}
func main()
{
    let task: PrintUglyNumber = PrintUglyNumber();
    // Test Case
    task.uglyNumber(20);
}
main();

Output

  1  2  3  4  5  6  8  9  10  12  15  16  18  20  24  25  27  30  32  36
// Kotlin Program
// Print Ugly Numbers
// By dynamic programming
class PrintUglyNumber
{
    // Returns minimum value of two numbers
    fun findMin(a: Int, b: Int): Int
    {
        if (a > b)
        {
            // When b is small
            return b;
        }
        // When a is small
        return a;
    }
    fun uglyNumber(n: Int): Unit
    {
        // initial values 
        var no_2: Int = 2;
        var no_3: Int = 3;
        var no_5: Int = 5;
        // initial values of three location
        var two: Int = 0;
        var three: Int = 0;
        var five: Int = 0;
        // Use to store N ugly numbers
        val collection: Array < Int > = Array(n)
        {
            0
        };
        // Set first ugly number
        collection[0] = 1;
        var i: Int = 1;
        while (i < n)
        {
            // Assign that minimum value of three numbers
            collection[i] = this.findMin(no_2, 
                             this.findMin(no_3, no_5));
            if (no_2 == collection[i])
            {
                two += 1;
                no_2 = collection[two] * 2;
            }
            if (no_3 == collection[i])
            {
                three += 1;
                no_3 = collection[three] * 3;
            }
            if (no_5 == collection[i])
            {
                five += 1;
                no_5 = collection[five] * 5;
            }
            i += 1;
        }
        i = 0;
        //Display ugly number
        while (i < n)
        {
            print(" " + collection[i]);
            i += 1;
        }
    }
}
fun main(args: Array < String > ): Unit
{
    val task: PrintUglyNumber = PrintUglyNumber();
    // Test Case
    task.uglyNumber(20);
}

Output

 1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36

Resultant Output Explanation

For the given C program and input N = 20, the output will be as follows:

1  2  3  4  5  6  8  9  10  12  15  16  18  20  24  25  27  30  32  36

These are the first 20 ugly numbers in ascending order, which satisfy the condition that their prime factors are only 2, 3, and 5.

Time Complexity Analysis

The time complexity of the given algorithm is O(n) because we loop from 1 to n to find the N ugly numbers. Within the loop, each iteration involves constant-time operations like finding the minimum and updating variables. Thus, the overall time complexity is linear, i.e., O(n).

In summary, the given program efficiently prints the first N ugly numbers using dynamic programming, with a time complexity of O(n).

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment