Posted on by Kalkicode
Code Number

# Find Super Ugly Number

In mathematics, an ugly number is a positive integer whose prime factors are limited to a specific set of prime numbers. The problem of finding the nth super ugly number involves finding the nth number that has prime factors only from a given set of factors. In this article, we will explore an algorithm to solve this problem and provide an explanation of the code snippet provided.

## Problem Statement

Given a positive integer n and a set of prime factors factors, we need to find the nth super ugly number. A super ugly number is a positive integer that can be expressed as a product of prime factors from the given set factors only. The factors can be repeated, and the super ugly number sequence must be in non-decreasing order.

## Explanation

Let's understand the problem with an example. Consider the set of prime factors factors = {3, 5, 7, 11}. We need to find the 15th super ugly number. To solve this, we iterate through all positive integers starting from 1 and check if each number is super ugly. We use the function `is_ugly` to determine if a number is super ugly or not. This function divides the number by each factor in the given set and updates the number until it becomes 1 or cannot be divided further by any of the factors. If the number eventually becomes 1, it means that it is a super ugly number, and we decrement the count of remaining super ugly numbers to find. Once we reach the desired count of super ugly numbers, we print the last number found.

## Algorithm

``````
1. Define a function co_factor(number, checker) that divides the given number by the checker until it is not divisible anymore.
2. Start with a count of super ugly numbers to find (n) and a counter variable (i) set to 1.
3. Iterate until the count of super ugly numbers to find becomes zero:
a. Check if the current number (i) is super ugly using the function is_ugly(i, factors, size).
b. If the number is super ugly:
i. Decrement the count of super ugly numbers to find (n) by 1.
ii. If the count becomes zero, print the current number (i) as the nth super ugly number.
c. Increment the counter variable (i) by 1 in each iteration.
4. End the loop.
```
```

## Pseudocode

``````
function co_factor(number, checker):
while number is divisible by checker:
divide number by checker
return number

function is_ugly(number, factors, size):
for i from 0 to size-1:
number = co_factor(number, factors[i])
return number

function super_ugly(n, factors, size):
i = 1
while n > 0:
if is_ugly(i, factors, size) == 1:
n = n - 1
if n == 0:
print i
i = i + 1

n = 15
factors = {3, 5, 7, 11}
size = length of factors
super_ugly(n, factors, size)
```
```

Let see an example for understand ugly numbers.

## Code Solution

Here given code implementation process.

``````//C Program
//Super Ugly Number
#include <stdio.h>

int co_factor(int number,int checker)
{
while(number%checker==0)
{
number/=checker;
}
return number;
}
int is_ugly(int number,int factor[],int size)
{
for (int i = 0; i < size; ++i)
{
number = co_factor(number,factor[i]);
}
return number;
}
void super_ugly(int n,int factor[],int size)
{

for (int i = 1; n > 0; ++i)
{
if(is_ugly(i,factor,size)==1)
{
n--;

if(n==0)
{
printf("%d\n",i );
}
}
}
}

int main()
{

int n = 15;
int factor[]={3, 5, 7, 11};
int size=sizeof(factor)/sizeof(factor);
super_ugly(n,factor,size);

return 0;
}```
```

#### Output

``55``
``````/*
//C++ Program
//Super Ugly Number
*/
#include<iostream>

using namespace std;
class Number {
public:
int co_factor(int number, int checker) {
while (number % checker == 0) {
number /= checker;
}
return number;
}
int is_ugly(int number, int factor[], int size) {
for (int i = 0; i < size; ++i) {
number = this->co_factor(number, factor[i]);
}
return number;
}
void super_ugly(int n, int factor[], int size) {
for (int i = 1; n > 0; ++i) {
if (this->is_ugly(i, factor, size) == 1) {
n--;
if (n == 0) {
cout << "  " << i;
}
}
}
}

};

int main() {
Number obj;
int n = 15;
int factor[] = {3,5,7,11};
int size = sizeof(factor) / sizeof(factor);
obj.super_ugly(n, factor, size);
}```
```

#### Output

``55``
``````/*
Java Program
Super Ugly Number
*/
public class Number {

public int co_factor(int number,int checker)
{
while(number%checker==0)
{
number/=checker;
}
return number;
}
public int is_ugly(int number,int []factor,int size)
{
for (int i = 0; i < size; ++i)
{
number = co_factor(number,factor[i]);
}
return number;
}
public void super_ugly(int n,int []factor,int size)
{

for (int i = 1; n > 0; ++i)
{
if(is_ugly(i,factor,size)==1)
{
n--;

if(n==0)
{
System.out.println("  "+i );
}
}
}
}

public static void main(String[] args) {
Number obj = new Number();

int n = 15;
int []factor={3, 5, 7, 11};
int size=factor.length;
obj.super_ugly(n,factor,size);

}
}```
```

#### Output

``55``
``````/*
C# Program
Super Ugly Number
*/
using System;
public class Number {

public int co_factor(int number,int checker)
{
while(number%checker==0)
{
number/=checker;
}
return number;
}
public int is_ugly(int number,int []factor,int size)
{
for (int i = 0; i < size; ++i)
{
number = co_factor(number,factor[i]);
}
return number;
}
public void super_ugly(int n,int []factor,int size)
{

for (int i = 1; n > 0; ++i)
{
if(is_ugly(i,factor,size)==1)
{
n--;

if(n==0)
{
Console.WriteLine("  "+i );
}
}
}
}

public static void Main(String[] args) {
Number obj = new Number();

int n = 15;
int []factor={3, 5, 7, 11};
int size=factor.Length;
obj.super_ugly(n,factor,size);

}
}```
```

#### Output

``55``
``````#Python3 Program
#Super Ugly Number
class Number :
def co_factor(self, number, checker) :
while (number % checker == 0) :
number /= checker;

return number;

def is_ugly(self, number, factor, size) :
i = 0;
while ( i < size ) :
number = self.co_factor(number, factor[i]);
i += 1
return number;

def super_ugly(self, n, factor, size) :
i = 1;
while ( n > 0) :
if (self.is_ugly(i, factor, size) == 1) :
n -= 1;
if (n == 0) :
print(i);
i += 1

def main() :
obj = Number();
n = 15;
factor = [3, 5, 7, 11];
size = len(factor);
obj.super_ugly(n, factor, size);

if __name__ == "__main__":
main()```
```

#### Output

``55``
``````#Ruby Program
#Super Ugly Number
class Number
def co_factor(number, checker)
while (number % checker == 0)
number = (number / checker).to_i
end
return number
end
def is_ugly(number, factor, size)
i = 0
while (i < size )
number = self.co_factor(number, factor[i])
i += 1
end
return number
end
def super_ugly(n, factor, size)
i = 1
while ( n > 0 )
if (self.is_ugly(i, factor, size) == 1)
n -= 1
if (n == 0)
print(i)
end
end
i += 1
end
end
end
def main()
obj = Number.new()
n = 15
factor = [3, 5, 7, 11]
size = factor.length
obj.super_ugly(n, factor, size)
end
main()```
```

#### Output

``55``
``````<?php
/*
Php Program
Super Ugly Number
*/
class Number {
public
function co_factor(\$number, \$checker) {
while (\$number % \$checker == 0) {
\$number = intval( \$number /\$checker);
}
return \$number;
}
public
function is_ugly(\$number, \$factor, \$size) {
for (\$i = 0; \$i < \$size; ++\$i) {
\$number = \$this->co_factor(\$number, \$factor[\$i]);
}
return \$number;
}
public
function super_ugly(\$n, \$factor, \$size) {
for (\$i = 1; \$n > 0; ++\$i) {
if (\$this->is_ugly(\$i, \$factor, \$size) == 1) {
\$n--;
if (\$n == 0) {
echo("  " + \$i);
}
}
}
}
}
function main() {
\$obj = new Number();
\$n = 15;
\$factor = array(3, 5, 7, 11);
\$size = count(\$factor);
\$obj->super_ugly(\$n, \$factor, \$size);
}
main();```
```

#### Output

``55``
``````/*
Swift 4
Super Ugly Number
*/
class Number {
func co_factor(_ number: Int, _ checker: Int) -> Int {
var num = number;
while (num % checker == 0) {
num = Int(num / checker);
}
return num;
}
func is_ugly(_ number: Int, _ factor: [Int] , _ size : Int) -> Int {
var num = number;
var i: Int = 0;
while ( i < size ) {
num = self.co_factor(num, factor[i]);
i += 1;
}
return num;
}
func super_ugly(_ n: Int, _ factor: [Int] , _ size : Int) {
var i: Int = 1;
var num = n;
while ( num > 0) {
if (self.is_ugly(i, factor, size) == 1) {
num -= 1;
if (num == 0) {
print(i);
}
}
i += 1;
}
}
}
func main() {
let obj: Number = Number();
let n: Int = 15;
let factor = [3, 5, 7, 11];
let size: Int = factor.count;
obj.super_ugly(n, factor, size);
}
main();```
```

#### Output

``55``
``````/*
Node Js Program
Super Ugly Number
*/
class Number {
co_factor(number, checker) {
while (number % checker == 0) {
number = parseInt(number / checker);
}

return number;
}
is_ugly(number, factor, size) {
for (var i = 0; i < size; ++i) {
number = this.co_factor(number, factor[i]);
}

return number;
}
super_ugly(n, factor, size) {
for (var i = 1; n > 0; ++i) {
if (this.is_ugly(i, factor, size) == 1) {
n--;
if (n == 0) {
process.stdout.write(" " + i);
}
}
}
}
}

function main(args) {
var obj = new Number();
var n = 15;
var factor = [3, 5, 7, 11];
var size = factor.length;
obj.super_ugly(n, factor, size);
}

main();```
```

#### Output

`` 55``
``````/*
Scala Program
Super Ugly Number
*/
class Number {
def co_factor(num: Int, checker: Int): Int = {
var number : Int = num;
while (number % checker == 0) {
number = (number / checker).toInt;
}
return number;
}
def is_ugly(num: Int, factor: Array[Int], size: Int): Int = {
var i : Int = 0;
var number : Int = num;
while (i < size) {
number = co_factor(number, factor(i));
i+=1;
}
return number;
}
def super_ugly(num: Int, factor: Array[Int], size: Int): Unit = {
var i : Int = 1;
var n : Int = num;
while (n > 0) {
if (is_ugly(i, factor, size) == 1) {
n -= 1;

if (n == 0) {
print(" " + i);
}
}
i+=1;
}
}
}
object Main {
def main(args: Array[String]): Unit = {
var obj: Number = new Number();
var n: Int = 15;
var factor: Array[Int] = Array(3, 5, 7, 11);
var size: Int = factor.length;
obj.super_ugly(n, factor, size);
}
}```
```

#### Output

`` 55``

## Output Explanation

For the given problem instance, we want to find the 15th super ugly number using the factors {3, 5, 7, 11}. The program iterates through the numbers starting from 1 until it finds the 15th super ugly number. The number 55 is the 15th super ugly number in this case. Therefore, the output of the code is 55.

## Time Complexity

The time complexity of the provided code depends on the value of n, the number of super ugly numbers to find. Let m be the average size of the prime factors array. The `is_ugly` function has a time complexity of O(m) since it iterates through the factors array. The `super_ugly` function runs until it finds all n super ugly numbers, so its time complexity is O(n * m). Therefore, the overall time complexity of the code is O(n * m).

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