We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.

- All Contests
- ProjectEuler+
- Project Euler #150: Searching a triangular array for a sub-triangle having minimum-sum.
- Discussions

# Project Euler #150: Searching a triangular array for a sub-triangle having minimum-sum.

# Project Euler #150: Searching a triangular array for a sub-triangle having minimum-sum.

Contest ends in

#### Sort by

recency

#### |

#### 23 Discussions

#### |

Please Login in order to post a comment

Surprisingly pass with

`O(n^4)`

solution.Read

`triangular(N)`

input.Compute all

`tetrahedral(N)`

subtriangles in`O(n^3)`

.Each subtriangle cost

`O(n)`

. Could be`O(1)`

by subtracting pre-computed row of sum.Sort all subtriangles and print first

`K`

.Do we have a case when K is greater then number of possible sums?

I have O(n^3) complexity but only the first case passes (used C++). This is a frustrating problem. It may even timeout in IO!

Lame that this cannot be done in python due to timeout. I did a non-recursive, dynamic programming solution that couldn't get a ton faster, still timeouts on every test case other than the sample.

Can't import numpy python 2.0.....