## Challenge

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
A non-empty zero-indexed array A consisting of N integers is given. Array A represents numbers on a tape. Any integer P, such that 0 < P < N, splits this tape into two non-empty parts: A[0], A[1], ..., A[P − 1] and A[P], A[P + 1], ..., A[N − 1]. The difference between the two parts is the value of: |(A[0] + A[1] + ... + A[P − 1]) − (A[P] + A[P + 1] + ... + A[N − 1])| In other words, it is the absolute difference between the sum of the first part and the sum of the second part. For example, consider array A such that: A[0] = 3 A[1] = 1 A[2] = 2 A[3] = 4 A[4] = 3 We can split this tape in four places: P = 1, difference = |3 − 10| = 7 P = 2, difference = |4 − 9| = 5 P = 3, difference = |6 − 7| = 1 P = 4, difference = |10 − 3| = 7 Write a function: class Solution { public int solution(int[] A); } that, given a non-empty zero-indexed array A of N integers, returns the minimal difference that can be achieved. For example, given: A[0] = 3 A[1] = 1 A[2] = 2 A[3] = 4 A[4] = 3 the function should return 1, as explained above. Assume that: N is an integer within the range [2..100,000]; each element of array A is an integer within the range [−1,000..1,000]. Complexity: expected worst-case time complexity is O(N); expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments). Elements of input arrays can be modified. |

## Attempt 1 (first solution that came to mind)

Ok, I know it would have a pretty bad runtime on larger sets, but it took me just a few minutes to come up with and time is money, so I submitted it…

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
class Solution { public int solution(int[] A) { var arr = A; var lowest = int.MaxValue; for (var p = 1; p < arr.Length; p++) { int head = 0, tail = 0; for (var a = 0; a < p; a++) { head += arr[a]; } for (var b = p; b < arr.Length; b++) { tail += arr[b]; } var sum = Math.Abs(head - tail); if (sum < lowest) lowest = sum; } return lowest; } } |

Result: 100**% Correctness, 33% Performance** because my solution failed on bigger datasets… and because the complexity is definitely not linear ^^

## Attempt 2 (lets see if I can just fool ’em)

So I thought: Why invest more time in a *real *solution when parallel taskprocessing which will cost me few seconds to implement… maybe I can trick Codilitys testrunner into thinking my runtime is good enough… worth a try.. Changed the first for loop to:

1 |
Parallel.ForEach(Enumerable.Range(0, arr.Length), (p) => {}) |

Result: Can’t run on testrunner (don’t know how they configured their runtime, but it seems *illegal* to spawn new threads.. mhmpf ok, so I really have to solve the problem for real then)

## Attempt 3 (2 loops)

Ok, we can reduce the loop to a single one and only calc the difference:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
class Solution { public int solution(int[] A) { var arr = A; var lowest = int.MaxValue; var tail = arr.Sum(); var head = 0; for (var p = 1; p < arr.Length; p++) { head += arr[p-1]; tail -= arr[p-1]; var sum = Math.Abs(head - tail); if (sum < lowest) lowest = sum; } return lowest; } } |

Result: **100% Correctness, 100% Performance… **okay, that wasn’t that hard… lets try sth. more challenging next time