# Codingame Solution: Block Number Sequence

You are given a number sequence as such: 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5, ... You need to find N-th number appearing in the sequence
Input
Single line: Number N, index of the number you need to find
Output
Single line: One integer representing N-th number in the sequence
Constraints
1<=n<=10¹⁴

## Solution

The block width of each increasing steadily and is 1, 2, 3, 4, ... Given the required index $$n$$, the block $$k$$ in which the index falls is given by

$\begin{array}{ccc} & \sum\limits_{i=1}^k &\geq n\\ \Leftrightarrow & \frac{1}{2}k(k+1)&\geq n\\ \end{array}$

Solving for $$k$$ results in $$k = \lfloor\frac{1}{2} (\sqrt{8n+1}-1)\rfloor$$. To calculate the actual squence, we calculate $$n - \frac{1}{2}k (k + 1) + 1$$, but since our index $$n$$ is 1-indexed, we need to subtract 1 from $$n$$ and arrive at the following implementation:

const f = n => {
const k = Math.floor((Math.sqrt(8 *n - 7) - 1) / 2);
return n - k * (k + 1) / 2;
};

« Back to problem overview