Difference between revisions of "Talk:TADM2E 3.28"
From Algorithm Wiki
(I don't think the solution is on this wiki yet.) |
(This actually seems to be doing 4 multiplications n times, so it is O(n).) |
||
| Line 17: | Line 17: | ||
answers[ backIndex] *= backProduct | answers[ backIndex] *= backProduct | ||
</source> | </source> | ||
| − | |||
| − | |||
| − | |||
Revision as of 11:34, 8 November 2015
I think this can be done in a single loop essentially taking two passes at once. Here is a Python snippet.
# O( n) - len( input_values) length = len( input_values) # the length of the input values answers = [1]*length # output values frontIndex = 0 # the index at which we have calculated the product of all preceding indexes frontProduct = 1 # the product of values preceding the front index backProduct = 1 # the product of values following the back index limit = length-1 backIndex = limit # the index at which we have calculated the product of all following values while( frontIndex < limit): frontProduct *= input_values[ frontIndex] backProduct *= input_values[ backIndex] frontIndex += 1 answers[ frontIndex] *= frontProduct backIndex -= 1 answers[ backIndex] *= backProduct
