Mapping integer to row in triangle A number triangle of order $n$ is made of rows of numbers in the following way:
The 1st row consists of the numbers 1,2,..,n.
For i > 1, the $i_{th}$ row consists $n - i + 1$ consecutive numbers, starting from the successive integer of the last number in the $(i-1)_{th}$ row. 
For example, for $n = 5$:
1st row: 1 2 3 4 5 
2nd row: 6 7 8 9
3rd row: 10 11 12
4th row: 13 14
5th row: 15
Given a triangle of order $n$ and an integer $1\leq k \leq \frac{n(n + 1)}{2}$, can I map $k$ to the row its in $\mathcal{O}(1) $?
For example, if $n=5$ and $k=11$, I want to map to return $3$. (because 11 is in the 3rd row)
 A: Yes.   $N=\frac{n(n+1)}{2}$ be the total number of elements. Look at it from the perspective of the last row.
Let $p+1$ be the the row number of the number k from the last row.  (i.e., the row number you want is $\mathbf{n-p}$). There are $N-k$ more elements after k  and they can be fit into a pyramid of $p+1$ rows. So, the question is, what is $p$? Well, we have $$\frac{p(p+1)}{2} \leq N-k \leq \frac{(p+1)(p+2)}{2}$$.  You just have to find $p$ satisfying this.  One way is $$p=[q]$$ where $[]$ is the floor function and q is the solution of the quadratic equation $$q^2+q-2(N-k)=0$$ 
Once you have $p$, you have your answer $n-p$. This calculation is $\mathcal{O}(1)$
A: It's a little easier to work with the triangle numbered in reverse order. To reduce to this problem, instead of finding the row of $k$, find the row of $n(n+1)/2-k$.
In the reversed setting, the row that $k$ is in is the smallest integer $m$ such that 
$$
k \le m(m+1)/2
$$
Since both sides are an integer, adding $1/8$ to the right does not affect this inequality, so this is the same as the smallest integer $m$ such that
$$
k \le m(m+1)/2 + 1/8
$$
Now the right side factors as $(m+\tfrac12)^2/2$, so the latter is equivalent to
$$
-\tfrac12+\sqrt{2k}\le m
$$
That is, you want the smallest $m$ so $-\tfrac12+\sqrt{2k}\le m$, which is just
$$
\lceil -\tfrac12 +\sqrt{2k}\,\rceil = (\sqrt{2k} \text{ rounded to nearest integer})
$$

This shows that your problem is equivalent to computing $\sqrt{2k}$ rounded to the nearest integer. Can this be done in constant time?

Seems to me like this is impossible, but I'm not so strong in computational complexity, so hopefully I've reduce the problem to a point where you can answer it.
