Minimalistic's blog

sum of triangular numbers
By Minimalistic, history, 8 years ago, In English

you have an an integer n such that 1<=n<= 10^12, find the sum of all triagular numbers that are less than or equal n,

time limit: 1 second

  • Vote: I like it
  • -35
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
8 years ago, hide # |
 
Vote: I like it +18 Vote: I do not like it

just binary search the index of the last triangular number <=n and use the hockey stick theorem

→ Reply
»
8 years ago, hide # |
← Rev. 5  
Vote: I like it -24 Vote: I do not like it

It can be solved in O(sqrt(n)). Triangular numbers is T(k)=k(k+1)/2, just increment k from 1 while T(k)<=n and get a sum of T(k)

If you have q queries, it can be solved in O(q*log(n)+sqrt(n)) with precompute prefix sums. Code?

And you can use binary search by last T(k), sum of T(k) from 1 to m is m(m+1)(m+2)/6

And you can solve in O(1) by solving equation m * (m+1) / 2 <= n ~ m^2 + m - 2 * n = 0.

Solution: m = (sqrt(8*n+1)-1)/2

→ Reply
  • »
    »
    8 years ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it -36 Vote: I do not like it

    yes please, I would like to see you approach

    → Reply
    • »
      »
      »
      8 years ago, hide # ^ |
      ← Rev. 2  
      Vote: I like it -10 Vote: I do not like it
      One query in `O(sqrt(n))`
      One query in `O(1)`
      → Reply
      • »
        »
        »
        »
        8 years ago, hide # ^ |
        ← Rev. 4  
        Vote: I like it +8 Vote: I do not like it

        I like that O(1) query, another thing that could be done here instead of using formula sqrt(8 * n + 1) — 1) / 2; it can be subs. by the following two lines of codes, 1-x=floor(sqrt(2*n)); 2-if(((x+1)*(x))/2>n)--x; x here is the number of the first triangular numbers <= n, then what is left is to calculate the sum of the first x triangular numbers. x=floor(sqrt(2*n));if(((x+1)*(x))/2>n)--x;

        → Reply
»
8 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

What's going on here? It is attack from one user with 15 accounts?

→ Reply