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:

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)
{
// Test Case
}
}``````

#### 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
}``````

#### 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()
{
// Test Case
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)
{
// Test Case
}
}``````

#### 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()
{
// Test Case
}
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()
{
// Test Case
}
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() :
#  Test Case

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()
#  Test Case
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
}
}``````

#### 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()
{
// Test Case
}
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
{
// Test Case
}``````

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

Categories
Relative Post