Difference between revisions of "Talk:TADM2E 3.28"
From Algorithm Wiki
Brownslink (talk | contribs) m (Single Pass in Python) |
(I don't think the solution is on this wiki yet.) |
||
| Line 17: | Line 17: | ||
answers[ backIndex] *= backProduct | answers[ backIndex] *= backProduct | ||
</source> | </source> | ||
| + | |||
| + | |||
| + | Both this suggestion and the solution given on the page still seem to be doing n-1 multiplications on n items, so they still seem to be n^2. --[[User:Murrayc2|Murrayc2]] ([[User talk:Murrayc2|talk]]) 06:17, 8 November 2015 (EST) | ||
Revision as of 11:17, 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
Both this suggestion and the solution given on the page still seem to be doing n-1 multiplications on n items, so they still seem to be n^2. --Murrayc2 (talk) 06:17, 8 November 2015 (EST)
