snippetcppMinor
Create index-less array product
Viewed 0 times
createarrayproductlessindex
Problem
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:
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";
}
}Solution
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:
previous code:
I believe this would give O(2N) time.
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
#include
#include
#include
#include
#include
#include
#include
namespace notstd {
template
auto to_vector(std::initializer_list il)
{
return std::vector(il);
}
}
static constexpr struct
{
template
void operator()(Iter first, Iter last) const
{
if (first != last) {
auto accum = std::accumulate(std::next(first), last,
EDIT: bugfix - (O3N) time with zero check:
#include
#include
#include
#include
namespace notstd {
template
auto to_vector(std::initializer_list il) {
return std::vector(il);
}
}
static constexpr struct {
template
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
auto mutate_copy(Container c, Algo algo) {
algo(std::begin(c), std::end(c));
return c;
};
template
auto mutate_copy(std::initializer_list il, Algo &&algo) {
return mutate_copy(notstd::to_vector(il),
std::forward(algo));
};
template
auto mutate_copy(std::array const &a, Algo &&algo) {
return mutate_copy(std::vector(a.begin(), a.end()),
std::forward(algo));
};
template
auto &mutate_inplace(Container &c, Algo algo) {
algo(std::begin(c), std::end(c));
return c;
};
template
std::ostream &emit(std::ostream &os, Container &&c) {
auto impl = [&os](auto first, auto last) {
using value_type = typename std::iterator_traits::value_type;
std::copy(first, last,
std::ostream_iterator(os, ", "));
};
impl(std::begin(c), std::end(c));
return os;
}
int main() {
emit(std::cout, mutate_copy({1, 2, 0, 4, 5}, other_products)) ar{10, 20, 30, 40, 50};
emit(std::cout, mutate_copy(ar, other_products)) {10, 11, 12, 13, 14};
emit(std::cout, mutate_copy(in, other_products)) foo{};
emit(std::cout, mutate_inplace(foo, other_products)) << std::endl;
}previous code:
I believe this would give O(2N) time.
#include
#include
#include
#include
#include
#include
template
auto other_products(Iter first, Iter last)
{
using type = typename std::iterator_traits::value_type;
auto mega_product = std::accumulate(first, last,
type(1), std::multiplies<>());
std::vector 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
auto other_products(Container&& c)
{
return other_products(std::begin(c), std::end(c));
}
template
auto other_products(std::initializer_list c)
{
return other_products(std::begin(c), std::end(c));
}
template
std::ostream& emit(std::ostream& os, Container&& c)
{
auto impl = [&os](auto first, auto last)
{
using value_type = typename std::iterator_traits::value_type;
std::copy(first, last,
std::ostream_iterator(os, ", "));
};
impl(std::begin(c), std::end(c));
return os;
}
int main()
{
emit(std::cout, other_products({1, 2, 3, 4, 5})) { 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
#include
#include
#include
#include
#include
#include
#include
namespace notstd {
template
auto to_vector(std::initializer_list il)
{
return std::vector(il);
}
}
static constexpr struct
{
template
void operator()(Iter first, Iter last) const
{
if (first != last) {
auto accum = std::accumulate(std::next(first), last,
Code Snippets
#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, #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;
}#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;
}Context
StackExchange Code Review Q#152731, answer score: 4
Revisions (0)
No revisions yet.