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).

Bookmark it! These icons link to social bookmarking sites where readers can share and discover new web pages.

Tags: interview quetsion·placements paper

1 Pa1 // Jun 25, 2008 at 5:30 pm

With Division operator, this would be a piece of cake…

Pa1
2 Esu // Jun 4, 2011 at 9:05 am

Easy, one can use that a = exp(ln(a)) or a = 10^log(a).
This pseudocode solution needs all A[i] to be nonzero:

TMP := 0
SN := 1
FOR i=0 TO N-1
TMP := TMP + ln( abs( A[i] ) )
SN := SN*sgn( A[i] )
END

FOR i=0 TO N-1
OUT[i] := TMP - ln( abs( A[i] ) )
OUT[i] := OUT[i]*SN*sgn( A[i] )
END

Where “ln” is the natural logarithm, “abs” is the absolute value and “sgn” is the sign.
This should work, though I didn’t test it.

Greetings, Esu
3 Pa1 // Jun 4, 2011 at 10:28 pm

@Esu,

What if one of the array element is zero ?

Also, what is the complexity of ur algo ?

- Pa1

Vamsi Pavan’s Place