Discussion on: Daily Coding Problem #2

Without being aware of possible constraints on the input numbers, a solution with division is most efficient as it conserves both memory (2 array allocations: input and output) and cpu (2 enumerations of the the array, O(2n) ~= O(n)). This was described by @severinson . Here it is in F#.

let calculate arr =
    let product = arr |> Array.reduce (*)
    arr |> Array.map (fun x -> product / x)

To consider a solution without division, understand that we are using division here to reverse a multiplication. An alternative is to choose not to multiply in the first place. But in order to do that, we move to an O( n² ) solution where we shape each element of the output array as we process the input. Then we can choose to selectively skip multiplication.

let calculate arr =
    // initialize the output array to 1s in prep for multiplication
    let output = Array.init (Array.length arr) (fun _ -> 1)
    arr |> Array.iteri (fun i x ->
        output |> Array.iteri (fun j y ->
            if i <> j then output.[j] <- y * x
        )
    )
    output

Note: This function is "pure", despite using mutation internally.

In some branches of mathematics certain operations are not reversible, such as matrix cross product in linear algebra. Perhaps better knowledge of that discipline would yield more efficient algorithms. However, all definitions of this sequence in OEIS use division for calculations.