3
\$\begingroup\$

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";   
   }  
}
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Have you tried arrays other than 1 2 3 4 5? What happens if your array is 2 3 4 5 6? \$\endgroup\$
    – JS1
    Jan 16 '17 at 3:24
4
\$\begingroup\$

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;
}
\$\endgroup\$
7
  • \$\begingroup\$ Your program crashes if the input array contains a zero. \$\endgroup\$
    – JS1
    Jan 16 '17 at 18:28
  • \$\begingroup\$ @JS1 oops - you're right. \$\endgroup\$ Jan 16 '17 at 18:55
  • \$\begingroup\$ @JS1 many thanks. O3 time now with a check for the two zero cases. \$\endgroup\$ Jan 16 '17 at 19:07
  • \$\begingroup\$ The other edge case is if the mega product overflows. For example, if the given array were: { 2^15, 2^15, 2^15 }, the answer would be 2^30 in each slot. But the mega product might overflow and become 0. I'm not sure that is within the scope of the question but I think the zero handling probably was. \$\endgroup\$
    – JS1
    Jan 16 '17 at 19:57
  • \$\begingroup\$ @JS1 yes I thought about the overflow case, but as N increases it becomes more of a problem whether or not we calculate the megaproduct. So like you I assumed that the boundary case was not part of the test. These questions normally have quite conservative limits on the input values \$\endgroup\$ Jan 16 '17 at 20:24
2
\$\begingroup\$

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();
}
\$\endgroup\$
2
  • \$\begingroup\$ @JS1 Next time just fix it. \$\endgroup\$ Jan 17 '17 at 16:39
  • \$\begingroup\$ I personally don't feel it's appropriate for people to edit each others' answers. I wouldn't want someone randomly editing my answer, even if I did have a bug in my code somewhere. Also, your solution still needs to handle the presence of zeros in the input. I'm not trying to give you a hard time. I made the same comment on the other answer and I upvoted both of you, for what it's worth. \$\endgroup\$
    – JS1
    Jan 17 '17 at 17:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.