### Daily Coding Problem 2

# Daily Coding Problem 2¶

## Problem Statement¶

Given an array of integers, return a new array such that each element at index i of the new array is the product of all the numbers in the original array except the one at i.

For example, if our input was [1, 2, 3, 4, 5], the expected output would be [120, 60, 40, 30, 24]. If our input was [3, 2, 1], the expected output would be [2, 3, 6].

Follow-up: what if you can't use division?

## Solution¶

### Strategy 1 - Division¶

*NOTE: I think this is a bad solution because one of the numbers could be 0.*

The solution with division is to find the total once, then divide it by each item in the list to find the resulting array.

```
// Easy way to work with any Nuget packages. Standard packages to load, regardless of solution.
#load "Paket.fsx"
Paket.Package
[ "FSharp.Collections.ParallelSeq"
"Expecto"
"Xplot.Plotly"
"XPlot.GoogleCharts"
]
#load "Paket.Generated.Refs.fsx"
#load "XPlot.GoogleCharts.fsx"
// Load the DLLs
#r "packages/FSharp.Collections.ParallelSeq/lib/net45/FSharp.Collections.ParallelSeq.dll"
#r "packages/Expecto/lib/net461/Expecto.dll"
/// Quick debugging
let tee f x = f x |> ignore; x
```

```
open System
// Use Parallel operations to speed up execution
open FSharp.Collections.ParallelSeq
/// Division method
let divisionRun ilist =
let total =
ilist
|> PSeq.fold (fun acc e -> acc * e) 1
// Cannot use PSeq because it re-orders the values in the list.
ilist
|> List.map (fun e -> total / e)
```

```
// Separate the run from the definitions because we don't want to re-compile definitions to run tests.
open Expecto
/// Basic brute-force tests to ensure the logic works correctly
let divisionTests =
testList "Division tests" [
test "[1; 2; 3; 4; 5]" {
Expect.equal (divisionRun [1; 2; 3; 4; 5]) [120; 60; 40; 30; 24] "[1; 2; 3; 4; 5]"
}
test "[3; 2; 1]" {
Expect.equal (divisionRun [3; 2; 1]) [2; 3; 6] "[3; 2; 1]"
}
test "[10; 15; 3; 7; 0]" {
Expect.throws (fun () -> divisionRun [10; 15; 3; 7; 0] |> ignore) "[10; 15; 3; 7; 0]"
}
]
runTests defaultConfig divisionTests
```

Excellent, our logic works!

Now, to try a different strategy.

### Strategy 2 - Multiplication¶

Create a list of lists where each list has the element in that position removed.

```
/// Remove the first occurrence of an element from a list. This is a safe method because
/// if the element does not occur, the list will be returned unchanged.
let removeFirstOccurrence e lst =
let rec loop accum = function
| [] -> List.rev accum
| h::t when e = h -> (List.rev accum) @ t
| h::t -> loop (h::accum) t
loop [] lst
/// Multiplication method
let multiplicationRun ilist =
ilist
|> List.map (fun e -> removeFirstOccurrence e ilist)
|> List.map (fun elst -> List.fold (fun acc e -> acc * e) 1 elst)
```

```
/// Basic subtraction tests to ensure the logic works correctly
let multiplicationTests =
testList "Multiplication tests" [
test "[1; 2; 3; 4; 5]" {
Expect.equal (multiplicationRun [1; 2; 3; 4; 5]) [120; 60; 40; 30; 24] "[1; 2; 3; 4; 5]"
}
test "[3; 2; 1]" {
Expect.equal (multiplicationRun [3; 2; 1]) [2; 3; 6] "[3; 2; 1]"
}
test "[10; 15; 3; 7; 0]" {
Expect.equal (multiplicationRun [10; 15; 3; 7; 0]) [0; 0; 0; 0; 3150] "[10; 15; 3; 7; 0]"
}
]
runTests defaultConfig multiplicationTests
```

As you can see, the multiplication strategy can handle more use cases than division strategy.

## Performance Comparison¶

Let's do some basic performance comparisons using BenchmarkDotNet.

```
/// Performance testing setup - change the input parameter if you want repeatable tests
/// NOTE: System.Random is NOT thread-safe. Using PSeq here is dubious at best.
let random = Random((int) DateTime.Now.Ticks &&& 0x0000FFFF)
let mutable randLock = Object()
/// Convenience method to generate random numbers safely.
let getNextRand (min, max) = lock randLock (fun () -> random.Next (min, max))
/// Represents inputs to the algorithms, with type int list list.
let inputGenerator numToGenerate minListLen maxListLen : int list list =
// Generate a single input
let generateOne () =
// list length is between minListLen and maxListLen entries
let listLen = getNextRand (minListLen, maxListLen)
// limiting each list element to be between 0 and 100
PSeq.init listLen
(fun _ -> getNextRand (1, 100))
|> PSeq.toList
PSeq.init numToGenerate (fun _ -> generateOne())
|> PSeq.toList
```

```
/// Division performance tests
let divisionPerformanceTest inputs =
[ for i in 0 .. List.length inputs-1 do
yield divisionRun inputs.[i] ]
|> ignore
/// Multiplication performance tests
let multiplicationPerformanceTest inputs =
[ for i in 0 .. List.length inputs-1 do
yield multiplicationRun inputs.[i] ]
|> ignore
/// Minimum length of list
let minListLength = 10
/// Maximum length of list
let maxListLength = 10000
/// Control variable for run: how many entries in each run?
let numToGenerate = 250
/// Control variable for run: how many runs?
let numberOfRuns = 6
/// Each run has different inputs
let inputs =
[ for i in 0 .. numberOfRuns-1 do
yield inputGenerator numToGenerate minListLength maxListLength ]
// Measure performance
let divStopwatch = System.Diagnostics.Stopwatch()
let multStopwatch = System.Diagnostics.Stopwatch()
let stopwatchResults =
[ for i in 0 .. numberOfRuns-1 do
divStopwatch.Reset()
divStopwatch.Start()
divisionPerformanceTest inputs.[i]
divStopwatch.Stop()
multStopwatch.Reset()
multStopwatch.Start()
multiplicationPerformanceTest inputs.[i]
multStopwatch.Stop()
let percentDiff =
100m
* (decimal(divStopwatch.ElapsedMilliseconds)
- decimal(multStopwatch.ElapsedMilliseconds))
/ decimal(divStopwatch.ElapsedMilliseconds)
yield
[ divStopwatch.Elapsed.ToString("c")
multStopwatch.Elapsed.ToString("c")
String.Format("{0:0.###}%", percentDiff) ]
]
```

And the results, with the Division strategy as the baseline method.

```
open XPlot.GoogleCharts
// Transform the results into inputs that GoogleCharts can use
let names = [ "Division"; "Multiplication"; "Percentage difference" ]
let results =
[ for i in 0 .. numberOfRuns-1 do
yield List.zip names stopwatchResults.[i] ]
// And plot the reuslts
results
|> Chart.Table
|> Chart.WithOptions(Options(showRowNumber = true))
|> Chart.WithLabels ("Technique"::[for i in 1 .. numberOfRuns do yield sprintf "Time %i" i])
```

## Conclusion¶

The multiplication technique is safer, but much, MUCH slower than division. So, in this case, maybe it's a good idea to go with the division and, for example, return a `Result`

or `Option`

result. For example, `Result<int, exn> list`

, `Result<int list, exn>`

, `Option<int> list`

, or `Option<int list>`

.

```
```

## Comments

## Post a Comment