How to get it working in O(n)?
Posted
by evermean
on Stack Overflow
See other posts from Stack Overflow
or by evermean
Published on 2010-05-26T07:50:31Z
Indexed on
2010/05/26
8:01 UTC
Read the original article
Hit count: 120
career-development
|interview-questions
|job-interview
|complexity
|algorithm-design
I came across an interview task/question that really got me thinking ... so here it goes:
You have 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).
I really tried to come up with a solution but I always end up with a complexity of O(n^2). Perhaps the is anyone smarter than me who can tell me an algorithm that works in O(n) or at least give me a hint...
© Stack Overflow or respective owner
