ကိုယ့်ကိုယ်ကိုမှလွဲ။ ခင်းကျင်း၏ထုတ်ကုန်


ခက်ခဲအဆင့် လွယ်ကူသော
မကြာခဏမေးတယ် Accolite အမေဇုံ DE Shaw မော်ဂန်စတန်လေ တေးသံစုံကဇါတ်
အခင်းအကျင်း သင်္ချာ

ပြProbleနာဖော်ပြချက်

“ ကိုယ့်ကိုယ်ကို မှလွဲ၍ ခင်းကျင်းခြင်း၏ထုတ်ကုန်များ” ပြproblemနာက၊ သင်သည် [] တစ်ခုကိုခင်းကျင်းပြသထားသည်။ အခြားပုံနှိပ်ထုတ်ဝေပါ အခင်းအကျင်း i [i] index of array မှာတူညီတဲ့အရွယ်အစား၏ p [] သည် array ၏ i 'index အညွှန်းကိန်း မှလွဲ၍ မူလ array ၏အစိတ်အပိုင်းအားလုံး၏ထုတ်ကုန်နှင့်ညီသည်။

နမူနာ

ကိုယ့်ကိုယ်ကိုမှလွဲ။ ခင်းကျင်း၏ထုတ်ကုန်

a [ ] = {1, 2, 3}
{6, 3, 2}

ရှင်းလင်းချက် - ခင်းကျင်းတဲ့အရွယ်အစားက ၃ ဖြစ်လို့၊ 3nd & 2rd element ကိုမြှောက်လျှင်ထုတ်ကုန်သည် ၆ ဖြစ်သည်။ အလားတူစွာကျွန်ုပ်တို့သည် 3nd & 6rd index element များအတွက်ဖြစ်သည်။ ထို့ကြောင့် output ကို {2, 3, 6} ဖြစ်ပါတယ်။

a [ ] = {4, 6, 1, 2}
{12, 8, 48, 24}

ဌာနခွဲနည်းလမ်းအသုံးပြုခြင်း

ဤနည်းလမ်းသည် array element များအားလုံးသည် 0 ထက် ပို၍ ကြီးသောကိစ္စတွင်သာထိရောက်သည်။

algorithm

1. Initialize an array a[] of size n.
2. Initialize a variable prod and store product of all the elements of the array a[] in it.
3. Create another array p[] to store products of all elements except self.
4. Traverse through array a[] and update the value of array p[] such that p[i] is equal to the division of a[i] and prod.
5. Print the array p[].

နံပါတ်များအားလုံး (array ထဲမှ element များ၊ input) ၏ထုတ်ကုန်ကိုသိမ်းဆည်းရန် variable တစ်ခုကိုသုံးလျှင်ပြနာကိုဖြေရှင်းနိုင်သည်။ ထို့နောက်လက်ရှိ element ကိုစုစုပေါင်းမြှောက်ခြင်းမှခွဲထုတ်လျှင် element တစ်ခုချင်းစီအတွက်အဖြေကိုရှာနိုင်သည်။

ကုဒ်

ကိုယ့်ကိုယ်ကိုမှလွဲ။ ခင်းကျင်းထုတ်ကုန်များအတွက် C ++ အစီအစဉ်

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

void prodArray(int a[], int n){
    int p[n], prod=1;
    
    //Find product of all elements of a[]
    for(int i=0; i<n; i++){
        prod = prod * a[i];
    }
    
    //Create array p[] to store
    //product except self
    for(int i=0; i<n; i++){
        p[i] = prod / a[i];
    }
    
    for(int i=0; i<n; i++){
        cout<<p[i]<<" ";
    }
}

int main() {
  int a[] = {4, 6, 1, 2};
  int n = sizeof(a)/sizeof(a[0]);
  prodArray(a,n);
  return 0;
}
12 8 48 24

မိမိကိုယ်ကို မှလွဲ၍ ခင်းကျင်းခြင်းထုတ်ကုန်အတွက် Java Program

class product{
    
    void prodArray(int a[], int n){
        int p[] = new int[n], prod=1;
        
        //Find product of all elements of a[]
        for(int i=0; i<n; i++){
            prod = prod * a[i];
        }
        
        //Create array p[] to store
        //product except self
        for(int i=0; i<n; i++){
            p[i] = prod / a[i];
        }
        
        for(int i=0; i<n; i++){
            System.out.print(p[i] + " ");
        }
    }
    
    public static void main(String[] args){
        product pro = new product();
    	int a[] = {4, 6, 1, 2};
    	int n = a.length;
    	pro.prodArray(a,n);
    }
}
12 8 48 24

ရှုပ်ထွေးဆန်းစစ်ခြင်း

အချိန်ရှုပ်ထွေး

အို (N)၊ ဘယ်မှာဒြပ်စင်အရေအတွက် N. ဘယ်မှာဒီတော့ဒီမှာကျနော်တို့ပထမ ဦး ဆုံး O (N) အချိန်အတွက် algorithm ကို run စေသည်သောခင်းကျင်းဖြတ်သန်းသွားသည်။

အာကာသရှုပ်ထွေးမှု

အို (၁)ဘာဖြစ်လို့လဲဆိုတော့ကျွန်တော်တို့ဟာအမြဲတမ်းအပိုအာကာသကိုသုံးခဲ့တဲ့အတွက်။ ကျနော်တို့က input ကိုသိမ်းဆည်းထားကတည်းကသို့သော် program တစ်ခုလုံးအဖြစ်အို (N) အာကာသကိုယူ။

ဌာနခွဲနည်းလမ်းမရှိဘဲ

မိမိကိုယ်ကိုပြproblemနာမှအပ Array ၏ထုတ်ကုန်အတွက် Algorithm

1. Initialize an array a[] of size n and a variable prod as 1.
2. Create another array p[] of the same size with all the elements as 1.
3. Traverse all the values from starting index to last index and update the values of array p[] such that p[i] = prod and prod = prod * a[i].
4. Initialize prod as 1 again and start traversing the array from last index to starting index.
5. Update array p[] such that p[i] = prod and prod = prod * a[i].
6. Print the array p[].

ကုဒ်

ကိုယ့်ကိုယ်ကိုမှလွဲ။ ခင်းကျင်းထုတ်ကုန်များအတွက် C ++ အစီအစဉ်

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

void prodArray(int a[], int n){
        
    if(n == 1) { 
        cout<<"0"; 
        return; 
    } 

    int prod = 1; 
    int p[n]; 

    /* Initialize the product array p[] as 1 */
    for(int j=0; j<n; j++) 
        p[j] = 1; 

    /* prod variable contains product of 
       elements on left side excluding a[i] */
    for(int i=0; i<n; i++) { 
        p[i] = prod; 
        prod *= a[i]; 
    } 

    /* Initialize prod to 1 for product on right side */
    prod = 1; 

    /* prod variable contains product of 
       elements on right side excluding a[i] */
    for(int i=n-1; i>=0; i--) { 
        p[i] *= prod; 
        prod *= a[i]; 
    } 
    for(int i=0; i<n; i++) 
        cout<<p[i]<<" ";

    return; 
}

int main() {
  int a[] = {4, 6, 1, 2};
  int n = sizeof(a)/sizeof(a[0]);
  prodArray(a,n);
  return 0;
}
12 8 48 24

မိမိကိုယ်ကို မှလွဲ၍ ခင်းကျင်းခြင်းထုတ်ကုန်အတွက် Java Program

class product{
    
    void prodArray(int a[], int n){
        
        if(n == 1) { 
            System.out.print("0"); 
            return; 
        } 
  
        int prod = 1; 
        int p[] = new int[n]; 
  
        /* Initialize the product array p[] as 1 */
        for(int j=0; j<n; j++) 
            p[j] = 1; 
  
        /* prod variable contains product of 
           elements on left side excluding a[i] */
        for(int i=0; i<n; i++) { 
            p[i] = prod; 
            prod *= a[i]; 
        } 
  
        /* Initialize prod to 1 for product on right side */
        prod = 1; 
  
        /* prod variable contains product of 
           elements on right side excluding a[i] */
        for(int i=n-1; i>=0; i--) { 
            p[i] *= prod; 
            prod *= a[i]; 
        } 
        for(int i=0; i<n; i++) 
            System.out.print(p[i] + " ");
  
        return; 
    }
    
    public static void main(String[] args){
        product pro = new product();
    	int a[] = {4, 6, 1, 2};
    	int n = a.length;
    	pro.prodArray(a,n);
    }
}
12 8 48 24

ရှုပ်ထွေးဆန်းစစ်ခြင်း

အချိန်ရှုပ်ထွေး

အို (N)၊ ဘာဖြစ်လို့လဲဆိုတော့ဒီမှာကျွန်တော်တို့ဟာ N. အရွယ်ရှိတဲ့ခင်းကျင်းမှုကိုဖြတ်သန်းသွားတယ်။

အာကာသရှုပ်ထွေးမှု

အို (၁)၊ ဘာဖြစ်လို့လဲဆိုတော့ကျွန်တော်တို့ဟာကန ဦး array ကိုသာပြောင်းပြီးအပိုအဆက်မပြတ်သာနေရာသာသုံးသောကြောင့်ဖြစ်သည်။ ပရိုဂရမ်တစ်ခုလုံးအနေဖြင့် O (N) နေရာယူသည်။ သို့သော် algorithm ကိုယ်တိုင်က O (1) space သာယူသည်။