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.

+ 0 comments 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`

.

+ 1 comment Do we have a case when K is greater then number of possible sums?

+ 0 comments 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!

+ 0 comments 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.

+ 0 comments Can't import numpy python 2.0.....

Load more conversations

Sort 23 Discussions, By:

Please Login in order to post a comment