# A Python solution (requires Python 2.5 or higher):

def mult(arr, num):

return reduce(lambda x,y: x*y if y!=num else x, arr)

arr = [mult(arr,i) for i in arr]

# O(n^2) time, O(n) space

View Allnum of num

8 Answers

▲

2

▼

# A Python solution (requires Python 2.5 or higher):

def mult(arr, num):

return reduce(lambda x,y: x*y if y!=num else x, arr)

arr = [mult(arr,i) for i in arr]

# O(n^2) time, O(n) space

▲

11

▼

Create two more arrays. One array contains the products of the elements going upward. That is, B[0] = A[0], B[1] = A[0] * A[1], B[2] = B[1] * A[2], and so on. The other array contains the products of the elements going down. That is, C[n] = A[n], C[n-1] = A[n] * A[n-1], and so on.

Now A[i] is simply B[i-1] * C[i+1].

▲

2

▼

def without(numbers):

lognums = [math.log10(n) for n in numbers]

sumlogs = sum(lognums)

return [math.pow(10, sumlogs-l) for l in lognums]

▲

7

▼

Here are my 2 cents to do this in memory without creating temporary arrays. The simple solution , if division was allowed, was multiple all the elements of the array i.e.

tolal = A[0]*A[1]]*....*A[n-1]

now take a loop of array and update element i with A[i] = toal/A[i]

Since division is not allowed we have to simulate it.

If we say X*Y = Z, it means if X is added Y times it is equal to Z e.g.

2*3 = 6, which also means 2+2+2 = 6. This can be used in reverse to find how mach times X is added to get Z. Here is my C solution, which take pointer to array head A[0] and size of array as input

void ArrayMult(int *A, int size)

{

int total= 1;

for(int i=0; i< size; ++i)

total *= A[i];

for(int i=0; i< size; ++i)

{

int temp = total;

int cnt = 0;

while(temp)

{

temp -=A[i];

cnt++;

}

A[i] = cnt;

}

}

Speed in O(n) and space is O(1)

▲

0

▼

#include

#define NUM 10

int main()

{

int i, j = 0;

long int val = 1;

long A[NUM] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

// Store results in this so results do not interfere with multiplications

long prod[NUM];

while(j < NUM)

{

for(i = 0; i < NUM; i++)

{

if(j != i)

{

val *= A[i];

}

}

prod[j] = val;

i = 0;

val = 1;

j++;

}

for(i = 0; i < NUM; i++)

printf("prod[%d]=%d\n", i, prod[i]);

return 0;

}

▲

1

▼

void fill_array ( int* array, size ) {

int i;

int t1,t2;

t1 = array[0];

array[0] = prod(1, size, array );

for(i = 1; i < size; i++){

t2 = array[i];

array[i] = prod(i, array.size(), array)*t1;

t1 *= t2;

}

int prod(start, end, array){

int i;

int val(1);

for(i = start; i < end; i++ )

val *= array[i];

return val;

}

* One or more comments have been removed. Please see our Community Guidelines or Terms of Service for more information.*

To comment on this, Sign In or Sign Up.

Would you like us to review something? Please describe the problem with this {0} and we will look into it.

Your feedback has been sent to the team and we'll look into it.

O(size of array) time & space:

First, realize that saying the element should be the product of all other numbers is like saying it is the product of all the numbers to the left, times the product of all the numbers to the right. This is the main idea.

Call the original array A, with n elements. Index it with C notation, i.e. from A[0] to A[n - 1].

Create a new array B, also with n elements (can be uninitialized). Then, do this:

Accumulator = 1

For i = 0 to n - 2:

Accumulator *= A[i]

B[i + 1] = Accumulator

Accumulator = 1

For i = n - 1 down to 1:

Accumulator *= A[i]

B[i - 1] *= Accumulator

Replace A with B

It traverses A twice and executes 2n multiplicates, hence O(n) time

It creates an array B with the same size as A, hence O(n) temporary space