Create index-less array product Source: careercup.com


  You are given an array of integers(with all valid input) You have to
  write a function which will produce another array, where the value in
  each index of the array will be the product of all values in the given
  array exccept that index. 
  
  Example
  
  Array 1: 1 2 3 4 5
  
  Array 2: 120 60 40 30 24
  
  Come up with a solution of \$O(n^2)\$ can you improve it?


I would like to get code review comments for my code:

void createIndexlessArrayProduct()
{ 
   int arr1[]= {1,2,3,4,5};
   int arr2[5];

   arr2[0] = 1;

   for(auto&amp; val : arr1)
   {
       arr2[0] *= val;
   }    

   for(int i = 1; i &lt; 5; ++i)
   {
       arr2[i] = arr2[0] / (i+1);
   }

   for( auto&amp; val : arr2)
   {
      std::cout &lt;&lt; val &lt;&lt; "\n";   
   }  
}
Isn't it quicker to compute the full product in linear time and then divide by each N?

EDIT: bugfix - (O3N) time with zero check:

#include &lt;numeric&gt;
#include &lt;array&gt;
#include &lt;vector&gt;
#include &lt;iostream&gt;

namespace notstd {

    template&lt;class T&gt;
    auto to_vector(std::initializer_list&lt;T&gt; il) {
        return std::vector&lt;T&gt;(il);
    }
}

static constexpr struct {
    template&lt;class Iter&gt;
    void operator()(Iter first, Iter last) const {
        if (first != last) {
            auto zeros = std::count(first, last, 0);
            switch (zeros) {
                case 0: {
                    auto accum = std::accumulate(std::next(first), last,
                                                 *first, std::multiplies&lt;&gt;());
                    std::transform(first, last,
                                   first,
                                   [accum](auto &amp;&amp;v) {
                                       return accum / v;
                                   });
                }
                    break;

                case 1: {
                    auto maybe_multiply = [](auto &amp;&amp;x, auto &amp;&amp;y) { return y == 0 ? x : x * y; };
                    auto accum = std::accumulate(first, last,
                                                 1, maybe_multiply);
                    std::transform(first, last,
                                   first,
                                   [accum](auto &amp;&amp;v) {
                                       if (v == 0)
                                           return accum;
                                       else
                                           return 0;
                                   });
                }
                    break;

                default: {
                    std::fill(first, last, 0);
                } break;
            }

        }
    }
} other_products {};

template&lt;class Container, class Algo&gt;
auto mutate_copy(Container c, Algo algo) {
    algo(std::begin(c), std::end(c));
    return c;
};

template&lt;class T, class Algo&gt;
auto mutate_copy(std::initializer_list&lt;T&gt; il, Algo &amp;&amp;algo) {
    return mutate_copy(notstd::to_vector(il),
                       std::forward&lt;Algo&gt;(algo));
};

template&lt;class T, std::size_t N, class Algo&gt;
auto mutate_copy(std::array&lt;T, N&gt; const &amp;a, Algo &amp;&amp;algo) {
    return mutate_copy(std::vector&lt;T&gt;(a.begin(), a.end()),
                       std::forward&lt;Algo&gt;(algo));
};

template&lt;class Container, class Algo&gt;
auto &amp;mutate_inplace(Container &amp;c, Algo algo) {
    algo(std::begin(c), std::end(c));
    return c;
};

template&lt;class Container&gt;
std::ostream &amp;emit(std::ostream &amp;os, Container &amp;&amp;c) {
    auto impl = [&amp;os](auto first, auto last) {
        using value_type = typename std::iterator_traits&lt;decltype(first)&gt;::value_type;
        std::copy(first, last,
                  std::ostream_iterator&lt;value_type&gt;(os, ", "));
    };
    impl(std::begin(c), std::end(c));
    return os;
}


int main() {

    emit(std::cout, mutate_copy({1, 2, 0, 4, 5}, other_products)) &lt;&lt; std::endl;
    emit(std::cout, mutate_copy({2, 3, 4, 5, 6}, other_products)) &lt;&lt; std::endl;
    emit(std::cout, mutate_copy({6, 5, 4, 3, 2}, other_products)) &lt;&lt; std::endl;

    std::array&lt;int, 5&gt; ar{10, 20, 30, 40, 50};
    emit(std::cout, mutate_copy(ar, other_products)) &lt;&lt; std::endl;
    emit(std::cout, mutate_inplace(ar, other_products)) &lt;&lt; std::endl;


    auto in = std::vector&lt;int&gt; {10, 11, 12, 13, 14};
    emit(std::cout, mutate_copy(in, other_products)) &lt;&lt; std::endl;

    std::vector&lt;int&gt; foo{};
    emit(std::cout, mutate_inplace(foo, other_products)) &lt;&lt; std::endl;
}


previous code:

I believe this would give O(2N) time.

#include &lt;numeric&gt;
#include &lt;vector&gt;
#include &lt;iostream&gt;
#include &lt;algorithm&gt;
#include &lt;functional&gt;
#include &lt;iterator&gt;

template&lt;class Iter&gt;
auto other_products(Iter first, Iter last)
{
    using type = typename std::iterator_traits&lt;Iter&gt;::value_type;
    auto mega_product = std::accumulate(first, last, 
                                        type(1), std::multiplies&lt;&gt;());

    std::vector&lt;type&gt; result;
    result.reserve(std::distance(first, last));
    std::transform(first, last,
                   std::back_inserter(result),
                   [mega_product](auto&amp;&amp; v)
                   {
                       return mega_product / v;
                   });
    return result;
}

//
// convenience specialisation for any container
//
template&lt;class Container&gt;
auto other_products(Container&amp;&amp; c)
{
    return other_products(std::begin(c), std::end(c));
}

template&lt;class Value&gt;
auto other_products(std::initializer_list&lt;Value&gt; c)
{
    return other_products(std::begin(c), std::end(c));
}

template&lt;class Container&gt;
std::ostream&amp; emit(std::ostream&amp; os, Container&amp;&amp; c)
{
    auto impl = [&amp;os](auto first, auto last)
    {
        using value_type = typename std::iterator_traits&lt;decltype(first)&gt;::value_type;
        std::copy(first, last, 
                  std::ostream_iterator&lt;value_type&gt;(os, ", "));
    };
    impl(std::begin(c), std::end(c));
    return os;
}

int main()
{

    emit(std::cout, other_products({1, 2, 3, 4, 5})) &lt;&lt; std::endl;
    emit(std::cout, other_products({2, 3, 4, 5, 6})) &lt;&lt; std::endl;
    emit(std::cout, other_products({6, 5, 4, 3, 2})) &lt;&lt; std::endl;

    auto in = std::vector&lt;int&gt; { 10, 11, 12, 13, 14 };
    emit(std::cout, other_products(in)) &lt;&lt; std::endl;

}


As a further refinement, I had a go are separating the concerns of 'in-place' or 'copy' operations from the actual mutating algorithm.

See what you think:

#include &lt;numeric&gt;
#include &lt;array&gt;
#include &lt;vector&gt;
#include &lt;iostream&gt;
#include &lt;algorithm&gt;
#include &lt;functional&gt;
#include &lt;iterator&gt;
#include &lt;initializer_list&gt;

namespace notstd {

    template&lt;class T&gt;
    auto to_vector(std::initializer_list&lt;T&gt; il)
    {
        return std::vector&lt;T&gt;(il);
    }
}

static constexpr struct
{
    template&lt;class Iter&gt;
    void operator()(Iter first, Iter last) const
    {
        if (first != last) {
            auto accum = std::accumulate(std::next(first), last,
                                         *first, std::multiplies&lt;&gt;());
            std::transform(first, last,
                           first,
                           [accum](auto&amp;&amp; v)
                           {
                               return accum / v;
                           });
        }
    }
} other_products {};

template&lt;class Container, class Algo&gt;
auto mutate_copy(Container c, Algo algo)
{
    algo(std::begin(c), std::end(c));
    return c;
};

template&lt;class T, class Algo&gt;
auto mutate_copy(std::initializer_list&lt;T&gt; il, Algo&amp;&amp; algo)
{
    return mutate_copy(notstd::to_vector(il),
                       std::forward&lt;Algo&gt;(algo));
};

template&lt;class T, std::size_t N, class Algo&gt;
auto mutate_copy(std::array&lt;T, N&gt; const&amp; a, Algo&amp;&amp; algo)
{
    return mutate_copy(std::vector&lt;T&gt;(a.begin(), a.end()),
                       std::forward&lt;Algo&gt;(algo));
};

template&lt;class Container, class Algo&gt;
auto&amp; mutate_inplace(Container&amp; c, Algo algo)
{
    algo(std::begin(c), std::end(c));
    return c;
};

template&lt;class Container&gt;
std::ostream&amp; emit(std::ostream&amp; os, Container&amp;&amp; c)
{
    auto impl = [&amp;os](auto first, auto last)
    {
        using value_type = typename std::iterator_traits&lt;decltype(first)&gt;::value_type;
        std::copy(first, last,
                  std::ostream_iterator&lt;value_type&gt;(os, ", "));
    };
    impl(std::begin(c), std::end(c));
    return os;
}


int main()
{

    emit(std::cout, mutate_copy({1, 2, 3, 4, 5}, other_products)) &lt;&lt; std::endl;
    emit(std::cout, mutate_copy({2, 3, 4, 5, 6}, other_products)) &lt;&lt; std::endl;
    emit(std::cout, mutate_copy({6, 5, 4, 3, 2}, other_products)) &lt;&lt; std::endl;

    std::array&lt;int, 5&gt; ar { 10, 20, 30 , 40, 50 };
    emit(std::cout, mutate_copy(ar, other_products)) &lt;&lt; std::endl;
    emit(std::cout, mutate_inplace(ar, other_products)) &lt;&lt; std::endl;


    auto in = std::vector&lt;int&gt; {10, 11, 12, 13, 14};
    emit(std::cout, mutate_copy(in, other_products)) &lt;&lt; std::endl;
}