- 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 Should have been explicitly mentioned to consider triangles with one element.

+ 5 comments I submitted my solution. I'm passing the first testcase, but I'm getting a timeout error on all other testcases. Is there a way to see what the second testcase is? Don't know if the problem is on my side or the system. Maybe my solution is too inefficient?

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

Sort 23 Discussions, By:

Please Login in order to post a comment