as n occurs n times
the last position of n = n(n+1)/2
last position of (n-1) = n(n-1)/2
so the position n(n-1)/2 + 1 to n(n+1)/2 contains n
kth position contains n and
n(n-1)/2 < k <= n(n+1)/2
or n(n-1) < 2k <= n(n+1)
n^2 - n < 2k <= n^2 + n
multiply by 4
4n^2 - 4n < 8k <= 4n^2 + 4n
(2n-1) ^2 - 1 < 8k <= (2n +1)^2 - 1
(2n-1) ^2 < 8k +1 <= (2n +1)^2
so n = (ceil(sqrt(8k+1) -1)/2
No comments:
Post a Comment