Create index-less array product

Question

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& val : arr1)
   {
       arr2[0] *= val;
   }    

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

   for( auto& val : arr2)
   {
      std::cout << val << "\n";   
   }  
}

Answer 1

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 <numeric>
#include <array>
#include <vector>
#include <iostream>

namespace notstd {

    template<class T>
    auto to_vector(std::initializer_list<T> il) {
        return std::vector<T>(il);
    }
}

static constexpr struct {
    template<class Iter>
    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<>());
                    std::transform(first, last,
                                   first,
                                   [accum](auto &&v) {
                                       return accum / v;
                                   });
                }
                    break;

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

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

        }
    }
} other_products {};

template<class Container, class Algo>
auto mutate_copy(Container c, Algo algo) {
    algo(std::begin(c), std::end(c));
    return c;
};

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

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

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

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


int main() {

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

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


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

    std::vector<int> foo{};
    emit(std::cout, mutate_inplace(foo, other_products)) << std::endl;
}

previous code:

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

#include <numeric>
#include <vector>
#include <iostream>
#include <algorithm>
#include <functional>
#include <iterator>

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

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

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

template<class Value>
auto other_products(std::initializer_list<Value> c)
{
    return other_products(std::begin(c), std::end(c));
}

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

int main()
{

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

    auto in = std::vector<int> { 10, 11, 12, 13, 14 };
    emit(std::cout, other_products(in)) << 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 <numeric>
#include <array>
#include <vector>
#include <iostream>
#include <algorithm>
#include <functional>
#include <iterator>
#include <initializer_list>

namespace notstd {

    template<class T>
    auto to_vector(std::initializer_list<T> il)
    {
        return std::vector<T>(il);
    }
}

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

template<class Container, class Algo>
auto mutate_copy(Container c, Algo algo)
{
    algo(std::begin(c), std::end(c));
    return c;
};

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

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

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

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


int main()
{

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

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


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

Answer 2

Don't use magic numbers

int arr2[5];  // 5 is a magic number.

You should get the code to work that out for you. If you change the size of arr1 then you should not need to modify arr2.

// C++17
int arr2[std::size(arr1)];

// C++14
int arr2[std::extent<decltype(arr1)>::value];

Don't re-use value.

The compiler is going to optimize your register assignments for you better than you ever will. So declare your variables as you need them.

arr2[0] = 1;

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

You don't need to put this in the array at location 0. Not this will also break if the first value if not 1.

int val = 1;

for(auto& item : arr1)
{
    val *= item;
}    

Use standard algorithms when you can.

Using standard algorithms expresses intent very clearly. Prefer to use these rather than manual loops.

int val = std::accumulate(std::begin(arr1), std::end(arr1), 1, std::multiplies<int>());

Result

I would re-write as:

#include <numeric>
#include <functional>
#include <iterator>
#include <iostream>

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

    int val = std::accumulate(std::begin(arr1), std::end(arr1), 1, std::multiplies<int>());

    std::transform(std::begin(arr1), std::end(arr1), std::begin(arr2), [&val](int item){return val/item;});

    for( auto& val : arr2)
    {   
        std::cout << val << "\n";
    }   
}


int main()
{
    createIndexlessArrayProduct();
}