સ્વ સિવાય એરેનું ઉત્પાદન


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે ભેગા એમેઝોન ડીઇ શw મોર્ગન સ્ટેન્લી ઓપેરા
અરે મઠ

સમસ્યા નિવેદન

“સ્વ સિવાય એરેનું ઉત્પાદન” સમસ્યા, જણાવે છે કે તમને એરે આપવામાં આવે છે []] બીજું છાપો એરે પી [] એરે પીના સમાન સૂચકાંક પરના મૂલ્ય જેવા એરે એમાં આઇથ ઈન્ડેક્સ પરના તત્વ સિવાય મૂળ એરેના તમામ ઘટકોના ઉત્પાદન સમાન છે.

ઉદાહરણ

સ્વ સિવાય એરેનું ઉત્પાદન

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

સમજૂતી: એરેનું કદ is છે, જો આપણે 3 જી અને 2 જી તત્વને ગુણાકાર કરીએ તો, ઉત્પાદન 3 છે. તે જ રીતે, આપણે 6 જી અને 2 જી અનુક્રમણિકા તત્વો માટે આ કરીએ છીએ. આમ આઉટપુટ {3, 6, 3} છે.

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

જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (એન), જ્યાં તત્વોની સંખ્યા એન છે. કારણ કે અહીં પહેલા આપણે એરેમાંથી પસાર થઈએ છીએ જે ઓ (એન) સમયમાં અલ્ગોરિધમનો ચલાવે છે.

અવકાશ જટિલતા

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

કોડ

સ્વ + સિવાય એરેના ઉત્પાદન માટે સી ++ પ્રોગ્રામ

#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

જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (એન), કારણ કે અહીં આપણે એરે કદ એન સાથે પસાર થયાં છે.

અવકાશ જટિલતા

ઓ (1), કારણ કે આપણે ફક્ત પ્રારંભિક એરે બદલી છે અને ફક્ત વધારાની સ્થિર જગ્યાનો ઉપયોગ કર્યો છે. પ્રોગ્રામ સમગ્ર રીતે O (N) જગ્યા લે છે પરંતુ એલ્ગોરિધમથી ફક્ત O (1) જગ્યા લે છે.