Problem

[harsh4u89]

There is an array A[N] of N numbers. You have to compose an array Output[N] such that Output[i] will be equal to multiplication of all the elements of A[N] except A[i]. For example Output[0] will be multiplication of A[1] to A[N-1] and Output[1] will be multiplication of A[0] and from A[2] to A[N-1].

Solve it without division operator and in O(n).

How can this problem be solved using c++?
Please discuss the approach

Thank you

[m4ster r0shi]

Solve it without division operator

hahaha, my guess is that your teacher wants to avoid a solution in which you'd multiply all elements of A and then put in output[i] that product divided by A[i].

I'd make a function that takes A[], Output[] and i as arguments. I'd initialize Output[i] to one. Then I'd make a for loop with j taking values from 0 to i-1 and set Output[i] to Output[i]*A[j]. Then I'd make another for loop with j taking values form i+1 to N-1 and again set Output[i] to Output[i]*A[j].

Then, I'd call this function for every i from 0 to N-1.

[pengfeibill]

#include <iostream>

using namespace std;

const int N = 5;

int A[N];
int Output[N];
int s1[N];
int s2[N];

int main()
{
int i;
for(i = 0; i < N; i++)
cin >> A[i];
s1[0] = A[0];
for(i = 1; i < N; i++)
s1[i] = s1[i - 1] * A[i];
s2[N - 1] = A[N - 1];
for(i = N - 2; i >= 0; i--)
s2[i] = s2[i + 1] * A[i];
Output[0] = s2[1];
Output[N - 1] = s1[N - 2];
for(i = 1; i < N - 1; i++)
Output[i] = s1[i - 1] * s2[i + 1];
for(i = 0; i < N; i++)
cout << Output[i] << " ";
cout << endl;
system("pause");
return 0;
}

[frunze1983]

It's match more better to solve the problem by your own efforts. However, if you post the question I'll give the answer which I have found recently:

Below is the working program in C++ which implements the solution:

#include <iostream>

int main()
{
const uint64_t N = 10;
uint64_t A[N] = {1, 2, 100, 4, 5, 4, 1, 1, 1, 2};
uint64_t B[N];
uint64_t E[N];
uint64_t output[N];
uint64_t Pb = 1;
uint64_t Pe = 1;
B[0] = 1;
E[N-1] = 1;
for (uint64_t i = 1; i < N; ++i) {
Pb = Pb * A[i - 1];
Pe = Pe * A[N - i];
B[i] = Pb;
E[N - 1 - i] = Pe;
}
for (uint64_t i = 0; i < N; ++i) {
output[i] = B[i] * E[i];
std::cout << output[i] << std::endl;
}
return 0;
}

[harsh4u89]

Yes Mr Frunze1983, You are absolutely right.

I will try to give more time to the questions.

Thank you very much