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.

Print Ugly number.

Code Solution

Here given code implementation process.

• C
• C++
• Java
• C#
• Python
• Ruby
• Php
• Swift 4
• Node Js
• Scala

//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[0]);
  super_ugly(n,factor,size);

  return 0;
}

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[0]);
  obj.super_ugly(n, factor, size);
}

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

  }
}

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

  }
}

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

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

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();

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();

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();

 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);
  }
}

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