Слагалица низа производа  


Ниво тешкоће Средњи
Често питани у Аццолите адобе амазонка јабука Асана Блацкроцк Блоомберг БитеДанце Цитадела ДЕ Схав еБаи еверноте Екпедиа фацебоок Голдман Сакс гоогле Хоузз интел ЛинкедИн лифт мицрософт Морган Стенли Нутаник радити пророчанство ПаиПал Паитм Куалтрицс Салесфорце САП СервицеНов Снапцхат Сплунк Таблеау твиттер Убер виза ВМваре Валмарт Лабс иахоо иандек
Ред Гроупон ЛеетЦоде

Изјава о проблему  

У производу поредак проблем слагалице морамо да конструишемо низ где је иth елемент ће бити производ свих елемената у датом низу, осим елемента у иth положај.

Пример  

Улазни 

5

10 3 5 6 2

Излаз

180 600 360 300 900

Алгоритам за решавање загонетке низа производа  

Корак КСНУМКС: Узмите векторски производ да бисте га ускладиштили.
а) Иницијализујте га векторским производом

Корак КСНУМКС: Направите два низа лево [] и десно [], лево чува производ елемената лево од и-тог индекса у низу. ригхт складишти производ елемената десно од и-тог индекса.

а. Иницијализујте први елемент лево као 1, а последњи елемент десно као 1.
б. са леве стране, ажурирајте и-те елементе левог низа производом и-тог елемента датог низа са претходним елементом левог низа. (лево [и] = лево [и-1] * низ [и-1]). тиме чува производ до претходног индекса у левом низу од датог низа.
ц. с десне стране ажурирајте и-те елементе десног низа производом и + 1-ог елемента датог низа следећим елементом десног низа. (десно [и] = десно [и + 1] * низ [и + 1]). тиме чува производ до претходног индекса у левом низу од датог низа.

Види такође
Претворите низ у цик-цак моду

Корак КСНУМКС:  Производ осим садашњег елемента биће исти као производ левих и десних елемената низа.
а) низ производа ће бити, продуцт [и] = лефт [и] * ригхт [и].

Објашњење за решавање загонетке низа производа  

Прво пређите низ од почетка и сачувајте умножак свих претходних елемената за сваки и. Сада пређите низ са задње стране и сачувајте збир са краја и сачувајте производ свих елемената након тог елемента.

лево [] = {10, 30, 150, 900, 1800}

десно [] = {1800, 180, 60, 12, 2}

Сада помоћу ових низова пронађите производ свих елемената у датом низу, осим елемента на и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

Анализа сложености  

Сложеност времена

Види такође
Напишите код да бисте утврдили да ли су два стабла идентична

Он) где је н број елемената присутних у низу. Овде прелазимо само 3 пута и проналазимо низ производа.

Сложеност простора

Он) јер користимо леви и десни низ за складиштење производа елемената.

Референце