0

Given an array of integers, return a new array such that each element at index i of the new array is the product of all the numbers in the original array except the one at i.

For example, if our input was [1, 2, 3, 4, 5], the expected output would be [120, 60, 40, 30, 24]. If our input was [3, 2, 1], the expected output would be [2, 3, 6].

Follow-up: what if you can't use division?

This is what I came up with, any suggestions or improvements upon my code would be very helpful. Thank you!

void arrProd(const int arr[], int size){
    int prod = 1;
    int arr2[size];

    for(int i = 0; i < size; i++){
        for(int j = 0; j < size; j++){
            if(j != i)
                prod = prod * arr[j];
        }
        arr2[i] = prod;
        prod = 1;
    }

    //Prints out final array
    for(int i = 0; i < size; i++){
        std::cout << arr2[i] << " ";
    }
    std::cout << std::endl;
}
Data
  • 1
  • 1
  • 1

3 Answers3

4

Even without divisions, you are not obliged to use this O(n^2) brute-force method.

One method is to calculate iteratively the products up to each index i, and the products back to index i:

forward[0] = arr[0]
forward[i] = arr[i] * forward[i-1]
backward[n-1] = arr[n-1]
backward[i] = arr[i] * backward[i+1]

Then simply:

prod[i] = forward[i-1] * backward[i+1]

Of course, you have to manage separately the cases:

prod[0] = backward[1]
prod[n-1] = forward[n-2]

Complexity: O(n)

Damien
  • 4,809
  • 4
  • 15
  • 20
  • Interesting, thank you! – Nathan Pierson Nov 05 '20 at 20:08
  • That is interesting, unfortunately my brain can not really process it without needing to draw it out :P – Lily Nov 05 '20 at 20:13
  • I wonder if you can do it at compile time with `constexpr`'s and/or templated functions – Lily Nov 05 '20 at 20:15
  • @ColonD I don't know. I am not a specialist of such operations at compile time. Generally, my programme calculations take several hours at run time. So, at compile time... – Damien Nov 05 '20 at 20:17
  • Don't worry about it, just speculation – Lily Nov 05 '20 at 20:18
  • 1
    @ColonD Think of it as building two arrays. `forward[i]` means "the cumulative product from `arr[0]` to `arr[i]`. `backward[i]` means "the cumulative product from `arr[i]` to `arr[n - 1]`. So therefore the product of everything except `arr[i]` is `forward[i] * backward[i]`. I think this method still needs some tuning--`forward[0] = 1`, for instance--but that should let you do it in a fixed number of O(n) passes. – Nathan Pierson Nov 05 '20 at 20:21
  • 1
    @NathanPierson Yes, `std::exclusive_scan()` can be used, see my answer. – EOF Nov 05 '20 at 20:28
2
#include <algorithm>
#include <numeric>
#include <functional>
#include <vector>
#include <execution>


template<typename T>
std::vector<T> exmul(std::vector<T> const &in)
{
  std::vector<T> u(in.size());
  std::exclusive_scan(in.cbegin(), in.cend(),
              u.begin(), T{1}, std::multiplies<>{});
  std::vector<T> d(in.size());
  std::exclusive_scan(in.crbegin(), in.crend(),
              d.begin(), T{1}, std::multiplies<>{});
  std::vector<T> r(in.size());
  std::transform(std::execution::par_unseq, u.cbegin(), u.cend(), d.crbegin(), r.begin(), std::multiplies<>{});
  return r;
}

std::vector<double> foo(std::vector<double>& in)
{
  return exmul(in);
}

#include <iostream>

int main()
{
  std::vector<double> v{4.0,7.0,80.0};
  auto r = foo(v);
  for (auto const &e : r) std::cout << e << '\n';
}

Note: If you're using this for a type where multiplication is not commutative, the second std::exclusive_scan() needs a binary_op multiplication that reverses the operands. Technically the entire approach requires associativity, which floating-point multiplication doesn't provide, so this is only an approximation.

EOF
  • 6,273
  • 2
  • 26
  • 50
  • I can't even begin to comprehend the description of exclusive_scan, nor thinking how it applies to everything else here. Your brain is 10x bigger than mines. – Lily Nov 05 '20 at 20:32
0

O(n) complexity with division (nor checking for zeroes)

template <size_t size>
void arrProd(const array<int, size>& arr) {
    int total_product = 1;
    for (size_t i = 0; i < arr.size(); ++i) {
        total_product *= arr[i];
    }
    // create output
    array<int, size> output;
    for (size_t i = 0; i < arr.size(); ++i) {
        output[i] = total_product / arr[i];
    }
    // cout output
    for (const auto output_value : output) {
        cout << output_value << endl;
    }
}

O(n^2) complexity without division

Your code is pretty much the same as my code:

template <size_t size>
void arrProd(const array<int, size>& arr) {
    // create output
    array<int, size> output;
    for (size_t outer = 0; outer < arr.size(); ++outer) {
        output[outer] = 1;
        for (size_t inner = 0; inner < arr.size(); ++inner) {
            if (inner == outer) {
                continue;
            }
            output[outer] *= arr[inner];
        }
    }
    // cout output
    for (const auto output_value : output) {
        cout << output_value << endl;
    }
}
Lily
  • 1,386
  • 2
  • 13
  • 16
  • 1
    I have proposed a O(n) method with no division. It may interest you – Damien Nov 05 '20 at 20:10
  • Indeed it has, I'll check it out in a second – Lily Nov 05 '20 at 20:11
  • 1
    The method with division (when alllowed !) is effectively the simpler. Pay attention to check that `arr[i] != 0` – Damien Nov 05 '20 at 20:19
  • I never even thought of `arr[i]` being `0`. I can not actually think of a simple solution so that the value at `arr[i]` would not be `0` and the rest would be `0`. – Lily Nov 05 '20 at 20:27
  • One possibility is to perform the multiplication of all numbers except the zeros, and to count the number of zeros ... – Damien Nov 05 '20 at 20:34
  • 1
    Hmm, I can only think of ugly code (three seperate branches for if zeros == 0, else if zeros == 1, then if zeros >= 2) none of those are ideal but I am clearly not in the right mindframe to think about anything efficient so I'm going to leave the thought at that :P – Lily Nov 05 '20 at 20:38