نفس کانسواءِ صف جي پيداوار


تڪليف جي سطح آسان
بار بار پڇڻ ۾ قبول ڪريو Amazon ڊي شاه مارگن Stanley ناٽڪ
ڪيريو Math

مسئلي جو بيان

"آرٽ جي پيداوار سواءِ پاڻ" جي مسئلي ، ٻڌائي ٿي ته توهان کي هڪ سٽ ڏني وئي آهي []. ٻيو پرنٽ ڪر صف p [] ساڳي سائيز وانگر جيئن ته صف جي ith انڊيڪس تي قيمت اصلي صف جي سڀني عنصرن جي پيداوار جي برابر آهي.

مثال

نفس کانسواءِ صف جي پيداوار

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

وضاحت: ڇاڪاڻ ته صف جو سائز 3. آهي جيڪڏهن اسان کي 2 واري ۽ ٽئين عنصر کي گهرايو وڃي ، پيداوار آهي 3. ساڳي طرح ، اسين اهو ڪم ڪري رهيا آهيون ٽئين ۽ ٽئين انڊيڪس عناصر. اھڙي طرح ٻاھر آھي {6 ، 2 ، 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

پيچيدگي تجزيي

وقت جي پيچيدگي

اي (اين) ، عناصر جو تعداد اين جي آهي ڇو ته هتي پهرين اسان صف ذريعي وياسين جيڪو الگورٿم کي 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

پيچيدگي تجزيي

وقت جي پيچيدگي

اي (اين) ، ڇاڪاڻ ته هتي اسان صف جي ذريعي پيچرو ڪيو آهي سائز اين.

خلائي پيچيدگي

اي (1) ، ڇاڪاڻ ته اسان صرف شروعاتي صف کي تبديل ڪيو آهي ۽ صرف اضافي مستقل جڳهه استعمال ڪئي آهي. مجموعي طور تي پروگرام O (N) اسپيس وٺي ٿو پر الگورٿم پاڻ کي فقط O (1) اسپيس وٺي ٿو.