ایک پروڈکٹ سرنی پہیلی  


مشکل سطح درمیانہ
اکثر پوچھا جاتا ہے اکٹھا کرنا ایڈوب ایمیزون ایپل آسن BlackRock بلومبرگ ByteDance درگ ڈی ای شا ای بے Evernote Expedia فیس بک گولڈمین سیکس گوگل Houzz انٹیل لنکڈ لفٹ مائیکروسافٹ مارگن سٹینلی نیوٹنکس اوپرا اوریکل پے پال پی ٹی ایم ایم کلاسیکی Salesforce SAP حاضر سروس Snapchat تقسیم جھانکی ٹویٹر Uber ویزا VMware والمارٹ لیبز یاہو Yandex
لڑی Groupon لیٹ کوڈ

مسئلہ یہ بیان  

کسی مصنوع میں صف پہیلی کا مسئلہ ہمیں ایک صف تیار کرنے کی ضرورت ہے جہاں میںth عنصر i میں عنصر کے علاوہ دیئے گئے صف میں موجود تمام عناصر کی پیداوار ہوگیth پوزیشن سے منافع کمانے کا موقع ملا۔

مثال کے طور پر  

ان پٹ 

5

10 3 5 6 2

آؤٹ پٹ

180 600 360 300 900

کسی پروڈکٹ آری پہیلی کو حل کرنے کیلئے الگورتھم  

1 مرحلہ: مصنوعات کو ذخیرہ کرنے کے لئے ایک ویکٹر پروڈکٹ لیں۔
a) اسے ویکٹر پروڈکٹ کے ذریعہ شروع کریں

2 مرحلہ: دو صفوں کو بائیں [] اور دائیں [] ، صفوں میں ith انڈیکس کے بائیں حصے میں عناصر کی بائیں ذخیرہ کی مصنوعات تیار کریں۔ حق ith انڈیکس کے دائیں عناصر کی مصنوعات کو اسٹور کرتا ہے۔

a. بائیں کے پہلے عنصر کو بطور 1 اور آخری عنصر کو بطور 1 شروع کریں۔
b. بائیں سے ، بائیں سرنی کے Iith عناصر کو اپ ڈیٹ کریں I-1 ویں عنصر کی مصنوع کے ساتھ بائیں سرے کے پچھلے عنصر کے ساتھ۔ (بائیں [i] = بائیں [i-1] * سرنی [i-1])۔ یہ کرکے ، یہ دیئے گئے صفوں سے بائیں صف میں پچھلے انڈیکس تک مصنوعات کو اسٹور کرتی ہے۔
c دائیں سے ، دائیں سرنی کے اگلے عنصر کے ساتھ دیئے گئے سرنی کے i + 1 ویں عنصر کی مصنوع کے ساتھ دائیں سرنی کے Iith عناصر کو اپ ڈیٹ کریں۔ (دائیں [i] = دائیں [i + 1] * سرنی [i + 1])۔ یہ کرکے ، یہ دیئے گئے صفوں سے بائیں صف میں پچھلے انڈیکس تک مصنوعات کو اسٹور کرتی ہے۔

یہ بھی دیکھتے ہیں
صف کو زیگ زیگ فیشن میں تبدیل کریں

3 مرحلہ:  موجودہ عنصر کے علاوہ پروڈکٹ بائیں اور دائیں صف کے عناصر کی مصنوع کی طرح ہوگی۔
a) مصنوع کی صف میں ، مصنوعات [i] = بائیں [i] * دائیں [i] ہوں گے۔

کسی پروڈکٹ آری پہیلی کو حل کرنے کے لئے وضاحت  

پہلے ، سرے کو شروع سے ہی عبور کریں اور ہر ایک کے لئے پچھلے عناصر کی مصنوعات کو اسٹور کریں۔ اب پیچھے سے سرنی کو عبور کریں اور آخر سے رقم جمع کریں اور اس عنصر کے بعد تمام عناصر کی مصنوع کو اسٹور کریں۔

بائیں [] = {10، 30، 150، 900، 1800}

حق [] = {1800 ، 180 ، 60 ، 12 ، 2}

اب ان صفوں کا استعمال کرتے ہوئے i میں عنصر کے علاوہ دیئے گئے صف میں موجود تمام عناصر کی پیداوار تلاش کریںth پوزیشن سے منافع کمانے کا موقع ملا۔

پروڈکٹ [] = {180 ، 600 ، 360 ، 300 ، 900}

عمل  

کسی پروڈکٹ آری پہیلی کو حل کرنے کے لئے سی ++ پروگرام

#include <bits/stdc++.h>
using namespace std;
int main()
{
  
  int n;
  cin>>n;
  int arr[n];
  for(int i=0;i<n;i++)
  {
      cin>>arr[i];
  }
  int left[n],right[n];
  vector<int> product;
  left[0] = 1; //initialize the first element as 1
  for(int i=1;i<n;i++)
  {
     left[i]=left[i-1]*arr[i-1]; // store the product till just previous index
  }
  right[n-1]=1;//initialzie the first element as 1
  for(int i=n-2;i>=0;i--)
  {
     right[i]=right[i+1]*arr[i+1]; //store the product till just next index
  } 
  for(int i=0;i<n;i++)
  {
     product.push_back(left[i]*right[i]);
  }
  for(int i=0;i<n;i++)//display the product array
  {
     cout<<product[i]<<"  "; 
  }
  return 0;
}

کسی پروڈکٹ آری پہیلی کو حل کرنے کے لئے جاوا پروگرام

import java.util.Arrays;
import java.util.Scanner;
import java.util.Vector;
class sum
{
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int arr[] = new int[n];
        for(int i=0;i<n;i++)
        {
            arr[i] = sr.nextInt();
        }
        int left[] = new int [n];
        int right[] = new int [n];
        Vector<Integer> product = new Vector<Integer>(); 
        left[0] = 1; //initialize the first element as 1
        for(int i=1;i<n;i++)
        {
           left[i]=left[i-1]*arr[i-1]; // store the product till just previous index
        }
        right[n-1]=1;//initialzie the first element as 1
        for(int i=n-2;i>=0;i--)
        {
           right[i]=right[i+1]*arr[i+1]; //store the product till just next index
        } 
        for(int i=0;i<n;i++)
        {
           product.add(left[i]*right[i]);
        }
        for(int i=0;i<n;i++)//display the product array
        {
           System.out.print(product.get(i)+"  "); 
        }
    }
}
5
10 3 5 6 2
180  600  360  300  900

پیچیدگی کا تجزیہ  

وقت کی پیچیدگی

یہ بھی دیکھتے ہیں
کوڈ لکھیں اس بات کا تعین کرنے کے لئے کہ اگر دو درخت ایک جیسے ہیں

اے (ن) جہاں n صف میں موجود عناصر کی تعداد ہے۔ یہاں ہم صرف 3 بار عبور کرتے ہیں اور مصنوعات کی صف کو تلاش کرتے ہیں۔

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

اے (ن) کیونکہ ہم عناصر کی مصنوعات کو ذخیرہ کرنے کیلئے بائیں اور دائیں صفوں کا استعمال کرتے ہیں۔

حوالہ جات