Супер потворне число


Рівень складності Medium
Часто запитують у Google
купа Математика

Напишіть програму для пошуку nth супер потворне число. Супер потворні числа - це позитивні числа, усі прості множники яких знаходяться в заданих простих числах простого списку розміром k.

Примітка:  1 вважається першим надпотворним числом.

Підхід 1: Груба сила

Головна думка

Ми будемо перебирати всі натуральні числа з 1, і ми будемо підтримувати змінну підрахунку, яка буде підраховувати кількість потворних чисел, які ми знайшли, і число, для якого підрахунок стає рівним n, ми надрукуємо це число.

Як перевірити, чи є число надмірно потворним?

Ми знайдемо всі прості дільники числа, і якщо всі його прості дільники присутні, то даний список "простих чисел", то число є надпотворним числом і навпаки.

Підхід 2: Динамічне програмування 

рішення

Це питання те саме, що об'єднання K відсортованих масивів.

Наприклад, ми маємо

Input:  n=7 and  primes = [3, 7, 11, 13]

Output: 21

Наш список буде продовжуватися так:

Супер потворне число

Алгоритм

  1. Оголосіть dp масив де dp [i] являє собою ith супер потворне число.
  2. Ініціалізуємо dp [1] = 1.
  3. Ініціалізуйте масив покажчиків розміром k, де покажчик [i] представляє покажчик ith просте число в даному масиві.
  4. Запустіть цикл для i в діапазоні від 2 до n:
    • Запустіть цикл для j в діапазоні від 0 до k-1, щоб знайти мінімальне значення dp [покажчик [j]] * простих чисел [j].
    • Оновити dp [i] = мінімальне значення.
    • Проведіть ітерацію над масивом покажчика та збільште ці індекси на 1, значення яких дорівнює мінімальному значенню.
  5. Повернути dp [n].

Реалізація

Програма C ++ для n-го супер потворного числа

#include <bits/stdc++.h>
using namespace std;
int nthSuperUglyNumber(int n, vector<int> &primes)
{
    vector<long long> dp(n + 1, 1);
    int k = primes.size();
    vector<int> pointer(k, 1);
    for (int i = 2; i <= n; i++)
    {
        long long mi = (1e18);
        for (int j = 0; j < k; j++)
        {
            long long temp = dp[pointer[j]] * primes[j];
            mi = min(mi, temp);
        }
        dp[i] = mi;
        for (int j = 0; j < k; j++)
        {
            long long temp = dp[pointer[j]] * primes[j];
            if (temp == mi)
            {
                pointer[j]++;
            }
        }
    }
    return dp[n];
}
int main()
{
    int n;
    cin >> n;
    int k;
    cin >> k;
    vector<int> primes(k);
    for (int i = 0; i < k; i++)
    {
        cin >> primes[i];
    }
    cout << "The nth super ugly number is: "<<nthSuperUglyNumber(n, primes) << endl;
}
7
4
3 7 11 13
The nth super ugly number is: 21

Програма JAVA для n-го супер потворного номера

import java.util.*;
public class Main
{
    public static int nthSuperUglyNumber(int n,int[] primes)
    {
        int[] dp=new int[n+1];
        for(int i=0;i<=n;i++){
            dp[i]=1;
        }
        int k = primes.length;
        int[] pointer = new int[k];
        for(int i=0;i<k;i++){
            pointer[i]=1;
        }
        for (int i = 2; i <= n; i++)
        {
            int mi = Integer.MAX_VALUE;
            for (int j = 0; j < k; j++)
            {
                int temp = dp[pointer[j]] * primes[j];
                mi = Math.min(mi, temp);
            }
            dp[i] = mi;
            for (int j = 0; j < k; j++)
            {
                int temp = dp[pointer[j]] * primes[j];
                if (temp == mi)
                {
                    pointer[j]++;
                }
            }
        }
        return dp[n];
    }

  public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      int k = sc.nextInt();
      int[] primes = new int[k];
      for(int i=0;i<k;i++){
            primes[i] = sc.nextInt();
        }
    System.out.println("The nth super ugly number is: "+nthSuperUglyNumber(n,primes));
  }
}
6
5
2 3 5 7 17
The nth super ugly number is: 6

Аналіз складності для n-го супер потворного числа

Часова складність

Є дві вкладені петлі, перша від 2 до N, а друга від 0 до k-1, тож складність часу становить O (n * k).

Космічна складність

Два масиви, один розміром n, а інший розміром k, отже, складність простору є O (n + k).

посилання