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 = *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:
|a||(ab) (ed)||(abc) (e)||abcd|
|(a) (edc)||(ab) (ed)||(abc) (e)||abcd|
|(edcb)||(a) (edc)||(ab) (ed)||(abc) (e)||abcd|