سپر بدصورت نمبر


مشکل سطح درمیانہ
اکثر پوچھا جاتا ہے گوگل
ڈھیر ریاضی

این تلاش کرنے کے لئے ایک پروگرام لکھیںth انتہائی بدصورت نمبر سپر بدصورت تعداد مثبت تعداد ہیں جن کے تمام اہم عوامل k کے سائز کی بنیادی فہرست میں شامل ہیں۔

نوٹ:  1 کو پہلا سپر بدصورت نمبر سمجھا جاتا ہے۔

نقطہ نظر 1: بروٹ فورس

مرکزی خیال

ہم 1 سے تمام قدرتی اعداد پر تکرار کریں گے اور ہم گنتی متغیر برقرار رکھیں گے جو ہمیں ملنے والی بدصورت تعداد کی گنتی کرے گا اور جس نمبر کے لئے گنتی n کے برابر ہوجائے گی ، ہم اس تعداد کو پرنٹ کریں گے۔

یہ چیک کیسے کریں کہ آیا نمبر ایک انتہائی بدصورت نمبر ہے؟

ہمیں تعداد کے سب سے اہم تقسیم پانے والے مل جائیں گے اور اگر اس کے تمام بنیادی طلاق دہندگان 'پرائمز' کی دی گئی فہرست موجود ہوں تو نمبر ایک انتہائی بدصورت نمبر ہے اور اس کے برعکس۔

نقطہ نظر 2: متحرک پروگرامنگ 

حل

یہ سوال وہی ہے جس میں K ترتیب شدہ صفوں کو ضم کرنا ہے۔

مثال کے طور پرہمارے پاس ہے

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

Output: 21

ہماری فہرست اس طرح جاری رہے گی:

سپر بدصورت نمبر

الگورتھم

  1. ڈی پی اعلان کریں صف جہاں dp [i] i کی نمائندگی کرتا ہےth انتہائی بدصورت نمبر
  2. شروع کریں dp [1] = 1۔
  3. سائز k کی ایک پوائنٹر صف کو شروع کریں جہاں پوائنٹر [i] i کے پوائنٹر کی نمائندگی کرتا ہےth دیئے گئے صف میں اول نمبر۔
  4. ایک لوپ چلائیں ، میرے لئے 2 سے n کی حد میں:
    • dp [پوائنٹر [j]] * پرائمز [j] کی کم از کم قیمت معلوم کرنے کے لئے 0 سے k-1 کی حد میں j کے لئے ایک لوپ چلائیں۔
    • تازہ کاری dp [i] = کم از کم قیمت۔
    • پوائنٹر سرنی پر تشخیص کریں اور ان اشاریہ جات میں 1 اضافہ کریں جن کی قیمت کم سے کم قیمت کے برابر ہے۔
  5. واپسی dp [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

نویں سپر بدصورت نمبر کے لئے جاوا پروگرام

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

نویں سپر بدصورت تعداد کے لئے پیچیدگی کا تجزیہ

وقت کی پیچیدگی

وہاں دو گھونسلے والے لوپ ہیں ، پہلے 2 سے N اور دوسرا 0 سے k-1 ، لہذا وقت کی پیچیدگی ہے O (n * k).

خلائی پیچیدگی

دو ارے ، ایک سائز ن میں سے ایک اور سائز کا دوسرا ، لہذا جگہ کی پیچیدگی ہے O (n + k).

حوالہ جات