Rayանգվածի արտադրանք, բացի ինքն իրեն


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Ակոլիտ Amazon ԴԵ Շոուն Morgan Stanley Օպերա
Դասավորություն Մաթեմատիկա

Խնդիրի հայտարարություն

«Rayանգվածի արտադրանք, բացի ինքն իրեն» խնդրից, նշվում է, որ ձեզ տրվում է զանգված []: Տպիր մեկ ուրիշը դասավորություն նույն չափի p [], այնպես, որ p զանգվածի i ցուցիչի p արժեքը հավասար է սկզբնական զանգվածի բոլոր տարրերի արտադրյալին, բացառությամբ a զանգվածի i ցուցիչի տարրին:

Օրինակ

Rayանգվածի արտադրանք, բացի ինքն իրեն

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

Բարդության վերլուծություն

Timeամանակի բարդություն

ՎՐԱ), որտեղ տարրերի քանակը N. քանի որ այստեղ մենք նախ անցանք այն զանգվածը, որը ստիպում է ալգորիթմը գործարկել O (N) ժամանակում:

Տիեզերական բարդություն

Ո (1), քանի որ մենք օգտագործում էինք անընդհատ լրացուցիչ տարածք: Բայց ծրագիրն, ընդհանուր առմամբ, տանում է O (N) տարածք, քանի որ մենք պահեցինք մուտքը:

Առանց բաժանման մեթոդի

Arանգվածի արտադրանքի ալգորիթմ, բացի ինքնախնդրից

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

Բարդության վերլուծություն

Timeամանակի բարդություն

ՎՐԱ), քանի որ այստեղ մենք թերթեցինք N զանգված ունեցող զանգվածի միջով:

Տիեզերական բարդություն

O (1), քանի որ մենք փոխել ենք միայն նախնական զանգվածը և օգտագործել ենք միայն լրացուցիչ հաստատուն տարածք: Րագիրն, ընդհանուր առմամբ, տանում է O (N) տարածք, բայց ալգորիթմը տանում է միայն O (1) տարածք: