Продукт на масив с изключение на самостоятелно


Ниво на трудност Лесно
Често задавани в Аколит Амазонка DE Шоу Morgan Stanley опера
Array Математически

Декларация за проблема

Проблемът „Продукт на масив с изключение на себе си“ гласи, че ви е даден масив a []. Отпечатайте друга масив p [] от същия размер, така че стойността при i-ти индекс на масив 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

Java програма за продукт на масив с изключение на самостоятелно

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

Java програма за продукт на масив с изключение на самостоятелно

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) пространство.