Talk:TADM2E 3.28
From Algorithm Wiki
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
Note by murrayc:
I think this should be the main solution, and I think this helps to visualise what is happening:
--Murrayc2 (talk) 07:29, 8 November 2015 (EST)a | b | c | d | e |
---|---|---|---|---|
Forwards: | ||||
a | ||||
a | ab | |||
a | ab | abc | ||
a | ab | abc | abcd | |
Backwards: | ||||
a | ab | (abc) (e) | abcd | |
a | (ab) (ed) | (abc) (e) | abcd | |
(a) (edc) | (ab) (ed) | (abc) (e) | abcd | |
(edcb) | (a) (edc) | (ab) (ed) | (abc) (e) | abcd |