اعداد زشت  


سطح دشواری ساده
اغلب در تحویل کالا گلدمن ساکس Paytm با
ریاضی

La مثبت تعداد که تنها فاکتورهای اصلی آنها 2 ، 3 یا 5 است به عنوان اعداد زشت شناخته می شوند. به عنوان مثال - 8 یک عدد زشت است زیرا تنها فاکتور اصلی 2 است اما 7 عدد زشتی نیست زیرا یک فاکتور اصلی 7 است. 1 استثنا گنجانده شده است.

با توجه به عدد صحیح n. n را پیدا کنیدth شماره زشت  

مثال

ورودی: 25

خروجی: 54

ورودی: 36

خروجی: 120

روش تکراری برای اعداد زشت  

الگوریتم اعداد زشت

  1.  تعداد متغیر = 1 را برای شمارش اعداد زشت آغاز کنید.
  2.  تکرار بیش از یک متغیر i = 1.
  3.  i را 1 افزایش دهید.
  4.  تقسیم آن توسط بزرگترین قدرتهای قابل تقسیم 2,3،XNUMX و 5 و نتیجه را برگردانید.
  5.  If ارزش نتیجه 1 است که i کاملا بر 2,3،5 یا XNUMX قابل تقسیم است ، تعداد را افزایش دهید.
  6.  مراحل 3,4،5 و XNUMX را تکرار کنید تا تعداد = n.
  7.  بازگشت من

پیچیدگی زمان: O (nlogn)

پیچیدگی فضا: O (1)

برنامه C ++ برای یافتن nth شماره زشت  

#include <bits/stdc++.h>
using namespace std;

/* Function to divide the integer by 
    greatest divisible powers of 2,3,5 */
int Div(int x, int y){ 
    while(x%y==0){ 
        x=x/y;  
    } 
    return x; 
}     
/* Function to get the ugly 
    number*/
int uglyNo(int n){ 
    int i=1;  
    int count=1;  
    
    while(n>count){ 
        i++;
        int p=i;
        p=Div(p,2); 
        p=Div(p,3); 
        p=Div(p,5); 
        if(p==1){ 
            count++;
        }  
    } 
    return i; 
} 
int main(){
    int n=9;
    cout<<uglyNo(n);
    return 0;
}
Output : 10

برنامه جاوا برای یافتن nth شماره زشت  

class Ugly{ 
    /* Function to divide the integer by 
        greatest divisible powers of 2,3,5 */
    static int Div(int x,int y){ 
        while(x%y==0) 
            x=x/y; 
        return x; 
    } 
    /* Function to get the ugly 
       number*/
    static int uglyNo(int n){ 
        int i=1; 
        int count=1;  
        while(n>count){ 
            i++; 
            int p=i;
            p=Div(p,2); 
            p=Div(p,3); 
            p=Div(p,5); 
            if(p==1){ 
                count++;
            }
        } 
        return i; 
    } 
    public static void main(String args[]){ 
        int n=9;
        int num = uglyNo(n); 
        System.out.println(num); 
    } 
} 
Output : 10

روش برنامه نویسی پویا برای اعداد زشت  

در این روش فقط آن اعدادی که ضرب 2,3،5 و XNUMX باشند در نظر گرفته می شوند.

به عنوان مثال - 2 × 1 ، 2 × 2 ، 2 × 3.

            3×1, 3×2, 3×3…….

            5×1, 5×2, 5×3…….

حداقل تعداد زشت از این s انتخاب می شودبرابریs در هر مرحله و نشانگر 1 افزایش می یابد.

الگوریتم

  1.  سه امتیاز دو ، سه و پنج را با صفر شروع کنید.
  2.  3 متغیر nm2 ، nm3 و nm5 را در نظر بگیرید تا مضرب بعدی 2,3،5 و XNUMX را ردیابی کنید.
  3.  برای ذخیره اعداد زشت با 1 در 0 آرایه ای با اندازه n ایجاد کنیدth شاخص.
  4.  یک متغیر را ابتدا مقدار اولیه آخرین عنصر در آرایه ذخیره می کند.
  5.  یک حلقه n-1 بار اجرا کنید و مراحل 6,7،8 و XNUMX را انجام دهید.
  6.  مقادیر nm2 ، nm3 ، nm5 را به ترتیب به صورت زشت [دو] * 2 ، زشت [سه] * 3 ، زشت [5] * 5 به روز کنید.
  7.  حداقل مقدار را از nm2 ، nm3 و nm5 انتخاب کرده و نشانگر مربوط به آن را افزایش دهید.           
  8.  حداقل مقدار را در متغیر next و آرایه ذخیره کنید.
  9.  بعد برگرد

توضیح

اجازه دهید n = 4

دو = 0 ، سه = 0 ، پنج = 0 ، بعدی = 1

زشت [n] = | 1 | ، nm2 = 2 ، nm3 = 3 ، nm5 = 5

تکرار اول

بعدی = دقیقه (nm2 ، دقیقه (nm3 ، nm5)) = دقیقه (2 ، دقیقه (3 ، 5)) = 2

زشت [1] = 2 ، دو = 1 ، nm2 = زشت [دو] x2 = زشت [1] x2 = 2 × 2 = 4

زشت [n] = | 1 | 2 |

بعدی = 2

تکرار دوم

بعدی = دقیقه (nm2 ، دقیقه (nm3 ، nm5)) = دقیقه (4 ، دقیقه (3 ، 5)) = 3

زشت [2] = 3 ، سه = 1 ، nm3 = زشت [سه] x3 = زشت [1] x3 = 3 × 3 = 9

زشت [n] = | 1 | 2 | 3 |

بعدی = 3

تکرار سوم

بعدی = دقیقه (nm2 ، دقیقه (nm3 ، nm5)) = دقیقه (4 ، دقیقه (9 ، 5)) = 4

زشت [3] = 4 ، دو = 2 ، nm2 = زشت [دو] x2 = زشت [2] x2 = 3 × 2 = 6

بعد از n-1 یعنی 3 تکرار-

زشت [n] = | 1 | 2 | 3 | 4 |

next = 4 // چهارمین عدد زشت چهار است

پیچیدگی زمان: O (N)

پیچیدگی فضا: O (N)

برنامه C ++ برای یافتن nth شماره زشت  

#include<bits/stdc++.h> 
using namespace std; 

/* Function to get the nth ugly number*/
int uglyNo(int n){ 
    int ugly[n], two=0, three=0, five=0; 
    int nm2=2, nm3=3, nm5=5, next=1; 
    
    ugly[0] = 1; 
    for (int i=1; i<n; i++){ 
        next = min(nm2,min(nm3,nm5));
        ugly[i] = next; 
        if(next==nm2){ 
            two++; 
            nm2 = ugly[two]*2; 
        } 
        if(next==nm3){ 
            three++; 
            nm3 = ugly[three]*3; 
        }  
        if(next==nm5){ 
            five++; 
            nm5 = ugly[five]*5; 
        }  
    }
    return next; 
} 
int main(){ 
    int n=9; 
    cout<<uglyNo(n); 
    return 0; 
}
Output : 10

برنامه جاوا برای یافتن nth شماره زشت  

import java.lang.Math; 
  
class Ugly{ 
    /* Function to get the nth ugly number*/
    int uglyNo(int n){ 
        int ugly[] = new int[n];
        int two=0, three=0, five=0; 
        int nm2=2, nm3=3, nm5=5, next=1; 
        
        ugly[0] = 1; 
        
        for(int i=1; i<n; i++){ 
            next = Math.min(nm2, Math.min(nm3, nm5)); 
              
            ugly[i] = next; 
            if(next == nm2){ 
               two = two+1; 
               nm2 = ugly[two]*2; 
            } 
            if(next == nm3){ 
               three = three+1; 
               nm3 = ugly[three]*3; 
            } 
            if(next == nm5){ 
               five = five+1; 
               nm5 = ugly[five]*5; 
            } 
        }
        return next; 
    } 
    public static void main(String args[]){ 
        int n = 9; 
        Ugly obj = new Ugly(); 
        System.out.println(obj.uglyNo(n)); 
    } 
} 
Output : 10

ارجاع سوالات مصاحبه

همچنین مشاهده کنید
حداکثر مجموع یک مسیر در یک مثلث عدد راست