Straightforward clear solution for Saw the Stick by DiZ - python coding challenges

Enable Javascript in your browser and then refresh this page, for a much enhanced experience.

Straightforward solution in Clear category for Saw the Stick by DiZ

def checkio(n):
    tn = [0]
    while tn[-1] < n: tn.append(tn[-1] + len(tn))   #Triangular numbers: O(n**.5)
    for e in range(1, len(tn)):                     #Calculate every possible sum
        for s in range(1, e):                       #with consecutive triangular numbers
            if sum(tn[s:e]) == n:
                return tn[s:e]                      #Global complexity: O(n**1.5)
    return []

April 23, 2014

Comments:

mlb00 on May 11, 2015, 6:28 p.m.
i like the tn[-1] < n expression! very clever! I solved mine in 21 lines and yours is still very clear in 8, nice job!

DiZ on May 12, 2015, 10:40 a.m.
Glad you like it! Nonetheless, I don't like it anymore. In regard to Nickie's fast solution, I would rewrite mine as following: <pre class='brush: python'>def checkio(n): s, tn, idx = 0, [0], {} while tn[-1] < n: idx[s] = len(tn) tn.append(tn[-1] + idx[s]) s += tn[-1] if s - n in idx: return tn[idx[s - n]:] return [] </pre> Still as short as previous solution but an amortized complexity in O(n)!

Dropbox

0 %

You ClassRoom Demo is Ready With the new tool CheckiO ClassRoom, you will be able to analyze your students' progress, have your own leaderboard, change missions order on the map, and so on.