Çirkin Nömrələr

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Çatdırılma Goldman Sachs Paytm
RiyaziyyatBaxılıb 29

The müsbət nömrələri yeganə əsas faktorları 2, 3 və ya 5-dir çirkin rəqəmlər kimi tanınır. Məsələn- 8 çirkin bir rəqəmdir, çünki yeganə əsas amil 2-dir, lakin 7, əsas amil 7 olduğu üçün çirkin bir rəqəm deyil. 1 istisna olmaqla daxil edilir.

Bir tam n verilmişdir. N-i tapınth Çirkin nömrə

misal

Input: 25

Çıxış: 54

Input: 36

Çıxış: 120

Çirkin nömrələr üçün təkrarlanan metod

Çirkin Nömrələr üçün Alqoritm

  1.  Çirkin rəqəmləri saymaq üçün dəyişən bir sayma = 1 başlayın.
  2.  İ = 1 dəyişən üzərində təkrarlayın.
  3.  İ-ni 1 artırın.
  4.  Bölün 2,3-ün ən böyük bölünən gücləri ilə 5 və nəticəni qaytarın.
  5.  If nəticənin dəyəri i olan 1 və ya 2,3-ə tamamilə bölünən 5-dir, sayını artırın.
  6.  Say = n olana qədər 3,4 və 5-ci addımları təkrarlayın.
  7.  Qayıt i.

Zamanın mürəkkəbliyi: O (nlogn)

Kosmik Mürəkkəblik: O (1)

N tapmaq üçün C ++ proqramıth Çirkin nömrə

#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

N tapmaq üçün Java proqramıth Çirkin nömrə

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

Çirkin Nömrələr üçün Dinamik Proqramlaşdırma Metodu

Bu metodda yalnız 2,3 və 5-ə vurulan rəqəmlər nəzərə alınır.

Məsələn- 2 × 1, 2 × 2, 2 × 3 …….

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

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

Minimum çirkin nömrə bu lərdən seçilirbərabərlikhər addımda s və göstərici 1 artır.

Alqoritm

  1.  Sıfıra yönəldən üç, iki, üç və beş göstəriciləri işə salın.
  2.  3 və 2-in növbəti çoxluğunu izləmək üçün 3 dəyişən nm5, nm2,3 və nm5 götürün.
  3.  Çirkin rəqəmləri 1-a 0 ilə saxlamaq üçün n ölçülü bir sıra düzəldinth index.
  4.  Son elementin dəyərini massivdə saxlayan növbəti dəyişəni başlatın.
  5.  N-1 dəfə bir döngə aparın və 6,7 və 8-ci addımları yerinə yetirin.
  6.  Nm2, nm3, nm5 dəyərlərini sırasıyla çirkin [iki] * 2, çirkin [üç] * 3, çirkin [5] * 5 olaraq yeniləyin.
  7.  Nm2, nm3 və nm5-dən minimum dəyəri seçin və onunla əlaqəli göstəricini artırın.           
  8.  Minimum dəyəri növbəti və massivdə dəyişəndə ​​saxlayın.
  9.  Növbəti qayıt.

Izahat

N = 4 olsun

iki = 0, üç = 0, beş = 0, sonrakı = 1

çirkin [n] = | 1 |, nm2 = 2, nm3 = 3, nm5 = 5

ilk təkrar

sonrakı = min (nm2, min (nm3, nm5)) = min (2, min (3, 5)) = 2

çirkin [1] = 2, iki = 1, nm2 = çirkin [iki] x2 = çirkin [1] x2 = 2 × 2 = 4

çirkin [n] = | 1 | 2 |

sonrakı = 2

ikinci təkrar

sonrakı = min (nm2, min (nm3, nm5)) = min (4, min (3, 5)) = 3

çirkin [2] = 3, üç = 1, nm3 = çirkin [üç] x3 = çirkin [1] x3 = 3 × 3 = 9

çirkin [n] = | 1 | 2 | 3 |

sonrakı = 3

üçüncü iteration

sonrakı = min (nm2, min (nm3, nm5)) = min (4, min (9, 5)) = 4

çirkin [3] = 4, iki = 2, nm2 = çirkin [iki] x2 = çirkin [2] x2 = 3 × 2 = 6

N-1-dən sonra 3 təkrar-

çirkin [n] = | 1 | 2 | 3 | 4 |

next = 4 // Dördüncü çirkin rəqəm dörddür

Zamanın mürəkkəbliyi: O (n)

Kosmik Mürəkkəblik: O (n)

N tapmaq üçün C ++ proqramıth Çirkin nömrə

#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

N tapmaq üçün Java proqramıth Çirkin nömrə

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

arayış Müsahibə Suallar

Translate »