सरणी के उत्पाद को छोड़कर स्व


कठिनाई स्तर आसान
में अक्सर पूछा एकोलाइट वीरांगना डीई शॉ मॉर्गन स्टेनली संचालित
ऐरे मठ

समस्या का विवरण

"स्वयं को छोड़कर, सरणी का उत्पाद" बताता है कि आपको एक सरणी दी गई है []। दूसरा प्रिंट करें सरणी p [] समान आकार का ऐसा है जो कि सरणी p के i'th इंडेक्स पर मान a सरणी में i'th इंडेक्स पर तत्व को छोड़कर मूल सरणी के सभी तत्वों के उत्पाद के बराबर है।

उदाहरण

सरणी के उत्पाद को छोड़कर स्व

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

समस्या को हल किया जा सकता है यदि हम सभी नंबरों (सरणी, इनपुट) के तत्वों को स्टोर करने के लिए एक चर का उपयोग करते हैं। तब प्रत्येक तत्व का उत्तर पाया जा सकता है यदि कुल तत्व से कुल तत्व को विभाजित करें (अर्थात सभी तत्वों का उत्पाद)।

कोड

सी + + के अलावा सरणी के उत्पाद के लिए कार्यक्रम

#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) समय में चलाता है।

अंतरिक्ष जटिलता

ओ (1), क्योंकि हमने निरंतर अतिरिक्त स्थान का उपयोग किया। लेकिन एक पूरे के रूप में कार्यक्रम हे (एन) स्थान लेता है क्योंकि हम इनपुट संग्रहीत करते हैं।

बिना डिवीजन मेथड के

स्वयं समस्या को छोड़कर सरणी के उत्पाद के लिए एल्गोरिदम

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

कोड

सी + + के अलावा सरणी के उत्पाद के लिए कार्यक्रम

#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 वाले सरणी से गुजरते हैं।

अंतरिक्ष जटिलता

ओ (1), क्योंकि हमने केवल प्रारंभिक सरणी बदल दी है और केवल अतिरिक्त स्थिर स्थान का उपयोग किया है। एक पूरे के रूप में कार्यक्रम O (N) स्थान लेता है, लेकिन एल्गोरिथ्म केवल O (1) स्थान लेता है।