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;
};