Skip to content

Latest commit

 

History

History
48 lines (39 loc) · 2.09 KB

9.md

File metadata and controls

48 lines (39 loc) · 2.09 KB
Raw

9a

Given a list like this:

35
20
15
25
47
40
62
55
65
95
102
117
150
182
127
219
299
277
309
576

Find the number where: n26 === and possible sum of two numbers from n0 - n25

Going through the list splitting it and making a set of all possible sums is a valid thing to do given the size of the dataset. There should only be 25*25 calculations, so worst case scenario (the last item is the one), we'll do 1000 * 625 sums. Should be fine.

9b

We need to be slightly smarter this time around. Because now it's not about the sum of two numbers (2^25), but the sum of any of the items (25^25) that sum up to the number found previously. I think the smartest thing to do is to start at the number that is just under the number we found. Then add towards the right until we're 'over'. When we're over, shi... Scratch that. The numbers are not sorted and the sequence matters... We could brute force it. 12 core xeon, 24 threads, worst case scenario; 3,700,743,415,417,188,468,078,772,226,969,401.04... Hmmm. If our calculation took ps each, that would take us 42,832,678,419,180,422.08 days... There must be a smarter way to do this ;)...

Thinking...

  • We could make a tree, where ever element holds the sum of the two parents. That would be length n + n-1 + n-2 + n-3, which acc. to some math stack exhange means the nth triangular number. Apparently the rule is n(n+1)/2, which means 1000 (1001) / 2 - 500500. That works for me...

So, the plan is;

  • Take a bunch of numbers,

  • Construct a binary tree

  • Go from the root, if the number is too large, go to the smaller of the two, if it's too small, go to the larger

  • If it's exactly correct, walk the left side down to the leaf, and the right side down to the leaf. Sum those

  • So this worked. But only for small tree's. It was a superslow solution, even taking 100 lines of the list took forever. I will however try it overnight if it actually came up with the right solution.

The solution I ended up writing kept a rolling 'size'. We kept increasing the side as we went along, and then, when if we went over the size, decrease it from the left.