محصول آرایه به جز خود


سطح دشواری ساده
اغلب در همبستگی آمازون دی شاو مورگان استنلی اپرا
صف ریاضی

بیان مسأله

مسئله "محصول آرایه به جز خود" بیان می کند که به شما یک آرایه [] داده می شود. دیگری را چاپ کنید صف p [] از همان اندازه به طوری که مقدار در شاخص آرایه p برابر است با حاصلضرب تمام عناصر آرایه اصلی به جز عنصر در شاخص i در آرایه a.

مثال

محصول آرایه به جز خود

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

توضیح: از آنجا که اندازه آرایه 3 است. اگر عنصر 2 و 3 را ضرب کنیم ، محصول 6 است. به همین ترتیب ، این کار را برای عناصر شاخص 2 و 3 انجام می دهیم. بنابراین خروجی {6 ، 3 ، 2} است.

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

با استفاده از روش تقسیم

این روش فقط در مواردی موثر است که تمام عناصر آرایه همیشه بیشتر از 0 باشند.

الگوریتم

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[].

اگر از یک متغیر برای ذخیره محصول همه اعداد (عناصر موجود در آرایه ، ورودی) استفاده کنیم ، مشکل حل می شود. در صورت تقسیم عنصر فعلی از ضرب کل (یعنی حاصلضرب همه عناصر) ، جواب هر عنصر را می توان یافت.

رمز

++ 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

برنامه جاوا برای محصول آرایه به جز خود

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. است. زیرا در اینجا ابتدا ما از طریق آرایه ای عبور می کنیم که الگوریتم را در زمان O (N) اجرا می کند.

پیچیدگی فضا

O (1)، زیرا ما از فضای اضافی ثابت استفاده کردیم. اما برنامه از زمان ذخیره سازی ورودی ، فضای O (N) را می گیرد.

بدون روش تقسیم

الگوریتم محصول آرایه به جز خود مسئله

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

برنامه جاوا برای محصول آرایه به جز خود

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 عبور کردیم.

پیچیدگی فضا

O (1) ، زیرا ما فقط آرایه اولیه را تغییر داده و فقط از فضای ثابت اضافی استفاده کرده ایم. این برنامه به عنوان یک کل فضای O (N) را می گیرد اما الگوریتم تنها فضای O (1) را می گیرد.