Given an array of numbers return array of products of all other numbers no division

Question

I was asked this question in a job interview  and I d like to know how others would solve it  I m most comfortable with Java  but solutions in other languages are welcome   Given an array of numbers  nums  return an array of numbers products  where products i  is the product of all nums j   j    i  Input    1  2  3  4  5  Output    2 3 4 5    1 3 4 5    1 2 4 5    1 2 3 5    1 2 3 4            120  60  40  30  24   You must do this in O N  without using division

User · Answer

Here is another simple concept which solves the problem in O N            int   arr   new int    1  2  3  4  5           int   outArray   new int arr length            for int i 0 i lt arr length i                 int res Arrays stream arr  reduce 1   a  b  - gt  a   b               outArray i    res arr i                     System out println Arrays toString outArray

User · Answer

public static void main String   args        int   arr     1  2  3  4  5        int   result     1  1  1  1  1        for  int i   0  i  lt  arr length  i              for  int j   0  j  lt  i  j                  result i     arr j                      for  int k   arr length - 1  k  gt  i  k--                result i     arr k                       for  int i   result            System out println i             This solution i came up with and i found it so clear what do you think

User · Answer

Based on Billz answer--sorry I can t comment  but here is a scala version that correctly handles duplicate items in the list  and is probably O n    val list1   List 1  7  3  3  4  4  val view   list1 view zipWithIndex map   x   gt  list1 view patch x  2  Nil  1  reduceLeft       view force   returns       List 1008  144  336  336  252  252

User · Answer

One more solution  Using division  with twice traversal  Multiply all the elements and then start dividing it by each element

User · Answer

Translating Michael Anderson s solution into Haskell    otherProducts xs   zipWith     below above       where below   scanl     1   init xs             above   tail   scanr     1 xs

User · Answer

int   b   new int     1  2  3  4  5                int j  for int i 0 i lt b Length i        int prod   1    int s   b i     for j i j lt b Length-1 j            prod   prod   b j   1       int pos   i      while pos  -1      pos--    if pos  -1       prod   prod   b pos                         Console WriteLine   n Output is  0   prod

User · Answer

Here is a C implementation O n  time complexity  INPUT   include lt stdio h gt  int main         int x      printf  Enter The Size of Array           scanf   d   amp x       int array x-1  i       printf  Enter The Value of Array    n          for  i   0   i  lt   x-1   i                      printf  Array  d      i             scanf   d   amp array i                int left x-1    right x-1       left 0    1       right x-1    1         for  i   1   i  lt   x-1   i                      left i    left i-1    array i-1               printf   nThis is Multiplication of array i-1  and left i-1  n          for  i   0   i  lt   x-1   i                    printf  Array  d     d   Left  d     d n  i array i  i left i                  for  i   x-2   i  gt   0   i--                    right i    right i 1    array i 1              printf   nThis is Multiplication of array i 1  and right i 1  n          for  i   0   i  lt   x-1   i                    printf  Array  d     d   Right  d     d n  i array i  i right i                printf   nThis is Multiplication of Right i    Left i  n          for  i   0   i  lt   x-1   i                      printf  Right  d    left  d     d    d    d n  i i right i  left i  right i  left i                return 0        OUTPUT      Enter The Size of Array   5     Enter The Value of Array       Array 0    1     Array 1    2     Array 2    3     Array 3    4     Array 4    5      This is Multiplication of array i-1  and left i-1      Array 0    1   Left 0    1     Array 1    2   Left 1    1     Array 2    3   Left 2    2     Array 3    4   Left 3    6     Array 4    5   Left 4    24      This is Multiplication of array i 1  and right i 1      Array 0    1   Right 0    120     Array 1    2   Right 1    60     Array 2    3   Right 2    20     Array 3    4   Right 3    5     Array 4    5   Right 4    1      This is Multiplication of Right i    Left i      Right 0    left 0    120   1   120     Right 1    left 1    60   1   60     Right 2    left 2    20   2   40     Right 3    left 3    5   6   30     Right 4    left 4    1   24   24      Process returned 0  0x0    execution time   6 548 s     Press any key to continue

User · Answer

def productify arr  prod  i       if i  lt  len arr               prod append arr i - 1    prod i - 1   if i  gt  0 else prod append 1              retval   productify arr  prod  i   1              prod i     retval             return retval   arr i      return 1   arr    1  2  3  4  5     prod         productify arr  prod  0     print prod

User · Answer

Here s my attempt to solve it in Java  Apologies for the non-standard formatting  but the code has a lot of duplication  and this is the best I can do to make it readable   import java util Arrays   public class Products       static int   products int    nums            final int N   nums length          int   prods   new int N           Arrays fill prods  1           for  int            i   0  pi   1       j   N-1  pj   1                i  lt  N           amp  amp   j  gt   0                        pi    nums i        pj    nums j--                          prods i     pi      prods j     pj                       return prods            public static void main String   args            System out println              Arrays toString products 1  2  3  4  5                 prints   120  60  40  30  24             The loop invariants are pi   nums 0    nums 1      nums i-1  and pj   nums N-1    nums N-2      nums j 1   The i part on the left is the  prefix  logic  and the j part on the right is the  suffix  logic     Recursive one-liner  Jasmeet gave a  beautiful   recursive solution  I ve turned it into this  hideous   Java one-liner  It does in-place modification  with O N  temporary space in the stack   static int multiply int   nums  int p  int n        return  n    nums length    1         nums n     p   multiply nums  nums n     nums n    p   n   1               0  nums n     p      int   arr    1 2 3 4 5   multiply arr  1  0   System out println Arrays toString arr       prints   120  60  40  30  24

User · Answer

To be complete here is the code in Scala   val list1   List 1  2  3  4  5  for  elem  lt - list1  println list1 filter      elem  reduceLeft         This will print out the following   120 60 40 30 24   The program will filter out the current elem       elem   and multiply the new list with reduceLeft method  I think this will be O n  if you use scala view or Iterator for lazy eval

User · Answer

This is O n 2  but f  is soooo beautiful   List fold  fun seed i - gt  List mapi  fun j x - gt  if i j 1 then x else x i  seed              1 1 1 1 1             1  5

User · Answer

Coded up using EcmaScript 2015   use strict      Write a function that  given an array of n integers  returns an array of all possible products using exactly  n - 1  of those integers        Correct behavior  - the output array will have the same length as the input array  ie  one result array for each skipped element - to compare result arrays properly  the arrays need to be sorted - if array lemgth is zero  result is empty array - if array length is 1  result is a single-element array of 1  input array   1  2  3  1 2   2 1 3   3 2 3   6 result   2  3  6     class Test     setInput i        this input   i     return this       setExpected e        this expected   e sort       return this        class FunctionTester     constructor         this tests           new Test   setInput  1  2  3   setExpected  6  3  2          new Test   setInput  2  3  4  5  6   setExpected  3   4   5   6  2   4   5   6  2   3   5   6  2   3   4   6  2   3   4   5                 test f        console log  function    f name      this tests forEach  test  index    gt          var heading    Test      index             var actual   f test input        var failure   this  check actual  test         if   failure  console log heading   input    test input   output    actual        else console error heading  failure         return  failure               testChain f        this test f      return this         check actual  test          if   Array isArray actual   return  BAD  actual not array        if  actual length     test expected length  return  BAD  actual length is     actual length     expected      test expected length       if   actual every this  isNumber   return  BAD  some actual values are not of type number        if   actual sort   every isSame   return  BAD  arrays not the same       actual join            and      test expected join                    function isSame value  index            return value     test expected index                  isNumber v        return typeof v      number            Efficient  use two iterations of an aggregate product We need two iterations  because one aggregate goes from last-to-first The first iteration populates the array with products of indices higher than the skipped index The second iteration calculates products of indices lower than the skipped index and multiplies the two aggregates  input array  1 2 3    2 3 1     3 1 2  input array  2 3 4 5 6      3   4   5   6   2        4   5   6  2   3        5   6  2   3   4         6   2   3   4   5   big O   n - 2     n - 2    n - 2    3n - 6   gt  o 3n     function multiplier2 ns      var result         if  ns length  gt  1        var lastIndex   ns length - 1     var aggregate         for the first iteration  there is nothing to do for the last element     var index   lastIndex     for  var i   0  i  lt  lastIndex  i            if   i  aggregate   ns index        else aggregate    ns index        result --index    aggregate               for second iteration  there is nothing to do for element 0        aggregate does not require multiplication for element 1        no multiplication is required for the last element     for  var i   1  i  lt   lastIndex  i            if  i     1  aggregate   ns 0        else aggregate    ns i - 1        if  i     lastIndex  result i     aggregate       else result i    aggregate           else if  ns length     1  result 0    1    return result       Create the list of products by iterating over the input array  the for loop is iterated once for each input element  that is n for every n  we make  n - 1  multiplications  that becomes n  n-1  O n 2     function multiplier ns      var result         for  var i   0  i  lt  ns length  i          result push ns reduce  reduce  value  index    gt         i  amp  amp  index     1   value    edge case  we should skip element 0 and it s the first invocation  ignore reduce         index     i   reduce   value    multiply if it is not the element that should be skipped         reduce          return result       Multiply by clone the array and remove one of the integers  O n 2  and expensive array manipulation    function multiplier0 ns      var result         for  var i   0  i  lt  ns length  i          var ns1   ns slice      clone ns array     ns1 splice i  1     remove element i     result push ns1 reduce  reduce  value    gt  reduce   value          return result    new FunctionTester   testChain multiplier0  testChain multiplier  testChain multiplier2    run with Node js v4 4 5 like      node --harmony integerarrays js   function  multiplier0 Test  0  input    1  2  3   output    2  3  6   Test  1  input    2  3  4  5  6   output    120  144  180  240  360   function  multiplier Test  0  input    1  2  3   output    2  3  6   Test  1  input    2  3  4  5  6   output    120  144  180  240  360   function  multiplier2 Test  0  input    1  2  3   output    2  3  6   Test  1  input    2  3  4  5  6   output    120  144  180  240  360

User · Answer

int   arr1     1  2  3  4  5        int   product   new int arr1 Length                      for  int i   0  i  lt  arr1 Length  i                  for  int j   0  j  lt  product Length  j                          if  i    j                                product j    product j     0   arr1 i    product j    arr1 i

User · Answer

Well this solution can be considered that of C C    Lets say we have an array  a  containing n elements like a n  then the pseudo code would be as below   for j 0 j lt n j             prod j  1       for  i 0 i lt n i                     if i  j          continue            else         prod j  prod j  a i

User · Answer

I came up with 2 solutions in Javascript  one with division and one without  x000D   x000D     without division function methodOne arr      return arr map item   gt        return arr reduce  result  num    gt          if  num     item            result   result   num                return result        1              with division function methodTwo arr      var mul   arr reduce  result  num    gt        result   result   num      return result      1   return arr map item   gt  mul item      console log methodOne  1  2  3  4  5     console log methodTwo  1  2  3  4  5     x000D   x000D   x000D

User · Answer

Here is the ptyhon version      This solution use O n  time and O n  space   def productExceptSelf self  nums                type nums  List int       rtype  List int              N   len nums      if N    0  return        Initialzie list of 1  size N     l prods  r prods    1  N   1  N      for i in range 1  N         l prods i    l prods i-1    nums i-1       for i in reversed range N-1          r prods i    r prods i 1    nums i 1       result    x y for x y in zip l prods r prods       return result      This solution use O n  time and O 1  space   def productExceptSelfSpaceOptimized self  nums                type nums  List int       rtype  List int              N   len nums      if N    0  return        Initialzie list of 1  size N     result    1  N      for i in range 1  N         result i    result i-1    nums i-1       r prod   1     for i in reversed range N          result i     r prod       r prod    nums i       return result

User · Answer

Here is my solution in modern C    It makes use of std  transform and is pretty easy to remember   Online code  wandbox     include lt algorithm gt   include lt iostream gt   include lt vector gt   using namespace std   vector lt int gt  amp  multiply up vector lt int gt  amp  v       v insert v begin   1       transform v begin   1  v end                 v begin                 v begin   1                  auto const amp  a  auto const amp  b    return b a                        v pop back        return v     int main         vector lt int gt  v    1 2 3 4 5       auto vr   v       reverse vr begin   vr end         multiply up v       multiply up vr       reverse vr begin   vr end          transform v begin   v end                 vr begin                 v begin                    auto const amp  a  auto const amp  b    return b a                         for auto amp  i  v  cout  lt  lt  i  lt  lt

User · Answer

We can exclude the nums j   where j    i  from list first  then get the product of the rest  The following is a python way to solve this puzzle   from functools import reduce def products nums       return   reduce lambda x y  x   y  nums  i    nums i 1    for i in range len nums     print products  1  2  3  4  5      out   120  60  40  30  24

User · Answer

Just 2 passes up and down  Job done in O N   private static int   multiply int   numbers            int   multiplied   new int numbers length           int total   1           multiplied 0    1          for  int i   1  i  lt  numbers length  i                  multiplied i    numbers i - 1    multiplied i - 1                      for  int j   numbers length - 2  j  gt   0  j--                total    numbers j   1               multiplied j    total   multiplied j                      return multiplied

User · Answer

Precalculate the product of the numbers to the left and to the right of each element  For every element the desired value is the product of it s neigbors s products     include  lt stdio h gt   unsigned array 5      1 2 3 4 5    int main void    unsigned idx   unsigned left 5            right 5   left 0    1  right 4    1              calculate products of numbers to the left of  idx     for  idx 1  idx  lt  5  idx              left idx    left idx-1    array idx-1                         calculate products of numbers to the right of  idx     for  idx 4  idx--  gt  0              right idx    right idx 1    array idx 1              for  idx 0  idx  lt 5   idx              printf    u  Product  u  u     u n                    idx  left idx    right idx     left idx    right idx                 return 0      Result       a out  0  Product 1 120    120  1  Product 1 60    60  2  Product 2 20    40  3  Product 6 5    30  4  Product 24 1    24    UPDATE  now I look closer  this uses the same method as Michael Anderson  Daniel Migowski and polygenelubricants above

User · Answer

Here s a slightly functional example  using C                Func lt long gt    backwards   new Func lt long gt  input Length               Func lt long gt    forwards   new Func lt long gt  input Length                for  int i   0  i  lt  input Length    i                                var localIndex   i                  backwards i         gt   localIndex  gt  0   backwards localIndex - 1      1    input localIndex                   forwards i         gt   localIndex  lt  input Length - 1   forwards localIndex   1      1    input localIndex                              var output   new long input Length               for  int i   0  i  lt  input Length    i                                if  0    i                                        output i    forwards i   1                                       else if  input Length - 1    i                                        output i    backwards i - 1                                       else                                       output i    forwards i   1      backwards i - 1                                       I m not entirely certain that this is O n   due to the semi-recursion of the created Funcs  but my tests seem to indicate that it s O n  in time

User · Answer

Sneakily circumventing the  no divisions  rule   sum   0 0 for i in range a     sum    log a i    for i in range a     output i    exp sum - log a i

User · Answer

I have a solution with O n  space and O n 2  time complexity provided below    public static int   findEachElementAsProduct1 final int   arr             int len   arr length             int   product   new int len             Arrays fill product  1            int   product   IntStream generate    - gt  1  limit len  toArray              for  int i   0  i  lt  len  i                   for  int j   0  j  lt  len  j                       if  i    j                        continue                                     product i     arr j                                    return product

User · Answer

Here is a small recursive function  in C    to do the modofication in place  It requires O n  extra space  on stack  though  Assuming the array is in a and N holds the array length  we have  int multiply int  a  int fwdProduct  int indx        int revProduct   1      if  indx  lt  N           revProduct   multiply a  fwdProduct a indx   indx 1          int cur   a indx          a indx    fwdProduct   revProduct         revProduct    cur            return revProduct

User · Answer

Try this    import java util    class arrProduct    public static void main String args                      getting the size of the array          Scanner s   new Scanner System in               int noe   s nextInt             int out   new int noe            int arr     new int noe                getting the input array          for int k 0 k lt noe k                            arr k  s nextInt                         int val1   1 val2 1           for int i 0 i lt noe i                            int res 1                    for int j 1 j lt noe j                                       if  i j  gt  noe-1                                          int diff    i j - noe                        if arr diff   0                                            res   res   arr diff                                                            else                                       if arr i j   0                                            res  res arr i j                                                          out i  res                                     printing result          System out print  Array of Product                for int l 0 l lt out length l                            if l  out length-1                             System out print out l                                    else                                 System out print out l                                       System out print

User · Answer

- Recursive solution using sqrt n  subsets  Runs in O n    Recursively computes the solution on sqrt n  subsets of size sqrt n    Then recurses on the product sum of each subset  Then for each element in each subset  it computes the product with the product sum of all other products  Then flattens all subsets   Recurrence on the run time is T n    sqrt n  T sqrt n     T sqrt n     n  Suppose that T n   le  cn in O n    T n    sqrt n  T sqrt n     T sqrt n     n      le  sqrt n  c sqrt n    c sqrt n    n      le  c n   c sqrt n    n      le   2c 1  n      in  O n   Note that ceiling sqrt n   can be computed using a binary search  and O logn  iterations  if the sqrt instruction is not permitted  -   otherProducts         otherProducts  x     1  otherProducts  x y     y x  otherProducts a   foldl            zipWith   s p - gt  map   p  s  solvedSubsets subsetOtherProducts     where        n   length a        -- Subset size  Require that 1  lt  s  lt  n        s   ceiling   sqrt   fromIntegral n        solvedSubsets   map otherProducts subsets       subsetOtherProducts   otherProducts   map product subsets        subsets   reverse   loop a              where loop    acc   acc                 loop a acc   loop  drop s a    take s a  acc

User · Answer

My first try  in Python  O 2n    def product l       product   1     num zeroes   0     pos zero   -1        Multiply all and set positions     for i  x in enumerate l           if x    0              product    x             l i    1 0 x         else              num zeroes    1             pos zero   i        Warning  Zeroes ahead      if num zeroes  gt  0          l    0    len l           if num zeroes    1              l pos zero    product      else            Now set the definitive elements         for i in range len l                l i    int l i    product       return l   if   name         main         print   0  0  4        str product  0  0  4         print   3  0  4        str product  3  0  4         print   1  2  3        str product  1  2  3         print   2  3  4  5  6        str product  2  3  4  5  6         print   2  1  2  2  3        str product  2  1  2  2  3       Output    0  0  4     0  0  0   3  0  4     0  12  0   1  2  3     6  3  2   2  3  4  5  6     360  240  180  144  120   2  1  2  2  3     12  24  12  12  8

User · Answer

import java util Arrays   public class Pratik       public static void main String   args                int   array    2  3  4  5  6            OUTPUT  360  240  180  144  120         int   products   new int array length           arrayProduct array  products           System out println Arrays toString products               public static void arrayProduct int array    int products                  double sum   0  EPSILON   1e-9           for int i   0  i  lt  array length  i                sum    Math log array i             for int i   0  i  lt  array length  i                products i     int   EPSILON   Math exp sum - Math log array i                OUTPUT    360  240  180  144  120       Time complexity   O n       Space complexity  O 1

User · Answer

A neat solution with O n  runtime    For each element calculate the product of all the elements that occur before that and it store in an array  pre   For each element calculate the product of all the elements that occur after that element and store it in an array  post  Create a final array  result   for an element i   result i    pre i-1  post i 1

User · Answer

This is the recursive solution in Java    Called as following from main product a 1 0    public static double product double   a  double fwdprod  int index       double revprod   1      if  index  lt  a length           revprod   product2 a  fwdprod a index   index 1           double cur   a index           a index    fwdprod   revprod          revprod    cur            return revprod

User · Answer

Adding my javascript solution here as I didn t find anyone suggesting this  What is to divide  except to count the number of times you can extract a number from another number  I went through calculating the product of the whole array  and then iterate over each element  and substracting the current element until zero     No division operation allowed    keep substracting divisor from dividend  until dividend is zero or less than divisor function calculateProducsExceptCurrent NoDivision input     var res         var totalProduct   1      calculate the total product   for var i   0  i  lt  input length  i         totalProduct   totalProduct   input i           populate the result array by  dividing  each value   for var i   0  i  lt  input length  i         var timesSubstracted   0      var divisor   input i       var dividend   totalProduct      while divisor  lt   dividend         dividend   dividend - divisor        timesSubstracted              res push timesSubstracted         return res

User · Answer

Here s a one-liner solution in Ruby    nums map    n   num -  n   inject

User · Answer

Here is my concise solution using python   from functools import reduce  def excludeProductList nums        after    reduce lambda x  y  x y  nums  i    for i in range 1  len nums        1      before    1     reduce lambda x  y  x y  nums   i   for i in range 1  len nums         zippedList    list zip before  after       finalList   list map lambda x  x 0  x 1   zippedList       return finalList

User · Answer

Here you go  simple and clean solution with O N  complexity   int   a    1 2 3 4 5       int   r   new int a length       int x   1      r 0    1      for  int i 1 i lt a length i             r i  r i-1  a i-1             for  int i a length-1 i gt 0 i--           x x a i           r i-1  x r i-1             for  int i 0 i lt r length i             System out println r i

User · Answer

C    O n    long long prod   accumulate in begin    in end    1LL  multiplies lt int gt      transform in begin    in end    back inserter res             bind1st divides lt long long gt     prod

User · Answer

Travel Left- Right and keep saving product  Call it Past  -  O n  Travel Right -  left keep the product  Call it Future  -  O n  Result i    Past i-1    future i 1  -  O n  Past -1    1  and Future n 1  1    O n

User · Answer

A variation in JavaScript using reduce   x000D   x000D  const getProduct   arr   gt  arr reduce  acc  value    gt  acc   value   x000D   x000D  const arrayWithExclusion    arr  node    gt  x000D    arr reduce  acc  val  j    gt   node     j       acc  val    acc        x000D   x000D  const getProductWithExclusion   arr   gt    x000D    let result       x000D   x000D    for  let i   0  i  lt  arr length  i    1    x000D      result push getProduct arrayWithExclusion arr  i     x000D      x000D   x000D    return result  x000D     x000D   x000D   x000D

User · Answer

Here is my code   int multiply int a   int n int nextproduct int i        int prevproduct 1      if i gt  n          return prevproduct      prevproduct multiply a n nextproduct a i  i 1       printf   i  d  gt   d n  i prevproduct nextproduct       return prevproduct a i      int main         int a    2 4 1 3 5       multiply a 5 1 0       return 0

User · Answer

I m use to C        public int   ProductExceptSelf int   nums                int   returnArray   new int nums Length           List lt int gt  auxList   new List lt int gt             int multTotal   0              If no zeros are contained in the array you only have to calculate it once         if  nums Contains 0                         multTotal   nums ToList   Aggregate  a  b    gt  a   b                for  int i   0  i  lt  nums Length  i                                  returnArray i    multTotal   nums i                                   else                       for  int i   0  i  lt  nums Length  i                                  auxList   nums ToList                    auxList RemoveAt i                   if   auxList Contains 0                                         returnArray i    auxList Aggregate  a  b    gt  a   b                                     else                                       returnArray i    0                                                                 return returnArray

User · Answer

An explanation of polygenelubricants method is  The trick is to construct the arrays  in the case for 4 elements                  1          a 0      a 0  a 1      a 0  a 1  a 2        a 1  a 2  a 3      a 2  a 3           a 3                   1       Both of which can be done in O n  by starting at the left and right edges respectively   Then multiplying the two arrays element by element gives the required result  My code would look something like this   int a N     This is the input int products below N   p 1  for int i 0 i lt N   i      products below i  p    p  a i      int products above N   p 1  for int i N-1 i gt  0 --i      products above i  p    p  a i      int products N      This is the result for int i 0 i lt N   i      products i  products below i  products above i       If you need to be O 1  in space too you can do this  which is less clear IMHO   int a N     This is the input int products N       Get the products below the current index p 1  for int i 0 i lt N   i      products i  p    p  a i         Get the products above the curent index p 1  for int i N-1 i gt  0 --i      products i   p    p  a i

User · Answer

Tricky    Use the following   public int   calc int   params     int   left   new int n-1  in   right   new int n-1   int fac1   1  int fac2   1  for  int i 0  i lt n  i           fac1   fac1   params i       fac2   fac2   params n-i       left i    fac1      right i    fac2     fac   1   int   results   new int n   for  int i 0  i lt n  i           results i    left i    right i       Yes  I am sure i missed some i-1 instead of i  but thats the way to solve it

User · Answer

ruby solution  a    1 2 3 4  result      a each   x  result push   a- x   reject  amp  zero   reduce        puts result

User · Answer

Here is simple Scala version in Linear O n  time    def getProductEff in Seq Int   Seq Int            create a list which has product of every element to the left of this element    val fromLeft   in foldLeft  1  Seq empty Int     ac  i      i   ac  1  ac  2    ac  1    2       create a list which has product of every element to the right of this element  which is the same as the previous step but in reverse    val fromRight   in reverse foldLeft  1 Seq empty Int     ac i      i   ac  1 ac  2    ac  1    2 reverse       merge the two list by product at index    in indices map i    fromLeft i    fromRight i        This works because essentially the answer is an array which has product of all elements to the left and to the right

User · Answer

I got asked this question recently  and whilst I couldn t get O N  during it  I had a different approach  unfortunately O N 2   but thought I d share anyway   Convert to List lt Integer gt  first   Loop through original array array length   times   Use a while loop to multiple the next set of required numbers   while  temp  lt  list size   - 1        res    list get temp       temp        Then add res to a new array  which of course you ve declared earlier   then add the value at array i  to the List  and continue so forth   I know this won t be of great use  but it s what I came up with under the pressures of an interview         int   array   new int   1  2  3  4  5       List lt Integer gt  list   Arrays stream array  boxed   collect Collectors toList         int   newarray   new int array length       int res   1      for  int i   0  i  lt  array length  i              int temp   i          while  temp  lt  list size   - 1                res    list get temp               temp                      newarray i    res          list add array i            res   1             Output   24  120  60  40  30

User · Answer

There also is a O N  3 2   non-optimal solution  It is quite interesting  though   First preprocess each partial multiplications of size N 0 5 this is done in O N  time complexity   Then  calculation for each number s other-values -multiple can be done in 2 O N 0 5  time why  because you only need to multiple the last elements of other   N 0 5  - 1  numbers  and multiply the result with   N 0 5  - 1  numbers that belong to the group of the current number   Doing this for each number  one can get O N  3 2   time   Example   4 6 7 2 3 1 9 5 8  partial results   4 6 7   168 2 3 1   6 9 5 8   360  To calculate the value of 3  one needs to multiply the other groups  values 168 360  and then with 2 1

[arrays] Given an array of numbers, return array of products of all other numbers (no division)

Examples related to arrays

Examples related to algorithm