Problem statement: https://www.codechef.com/RC122020/problems/RECNDNUM

My solution: https://www.codechef.com/viewsolution/32359646

To understand the solution, you need to know the size of each, let’s say ‘chunk’

```
Chunk 1 = 0 1: Size = 2
Chunk 2 = 0 1 2 1: Size = 4
Chunk 3 = 0 1 2 3 2 1: Size = 6
...
```

Now, solving for:

## N * N

The first time N occurs is during the time N*N. Here’s why:

A number N will first occur in the Nth chunk at the Nth index.

The index will be 2 + 4 + 6 + ... (for N-1 times) + N(we need to add the index as well)

Let’s distribute N to all the N-1 numbers.

Then, it’ll be 3 + 5 + 7 + ... (for N-1 times) + 1 since we have a leftover.

Now, the sum is 1 + 3 + 5 + ... (for N times).

The sum of the first N odd numbers = N*N

## Floor(K/2) * 2*N

Notice the differences between the last index of any number in a chunk and the first index of the same element in the next chunk. It’s always 2*Number. And that will occur Floor(K/2) times when finding the Kth occurrence.

So, we have to add Floor(K/2)*2*N.

## Ceil(K/2) * Ceil(K/2-1)

Note: We have to remove Floor(K/2) from K (since it was taken care of above), which would be Ceil(K/2).

We only have to add the differences of the first index of an element and the last index of an element in each chunks. Notice that the differences start at `0`

and increase by 2 for every chunk after it. Therefore, the sum will be:

`0 + 2 + 4 + 6 ...`

for Ceil(K/2) times

That is equal to Ceil(K/2) * Ceil(K/2-1)

And therefore, we get the formula N*N + Floor(K/2) * 2 * N + Ceil(K/2) * Ceil(K/2-1)

**The only exception if for 0, in which case you have to print K*(K-1)**

Hope you understood my editorial!

Also, do rate this post, since it’s my first time writing an editorial

And feel free to ask any doubts or give me any suggestion!