Given a number N, an array is created by first adding all the odd numbers, and then adding all the even numbers below N, How do we find the number at a given position K?
For example consider N = 10, the array is [1, 3, 5, 7, 9, 2, 4, 6, 8, 10], the number at position K = 3 is 5, similarly at K = 6, the number is 2 etc.
Let us look at a solution for this. First of all, we need not build the entire array for finding out a number at a given position. We can simply find a formula to calculate the number, as the array can be divided into two halves, and both of them are in arithmetic progression.
If the given index is in first half, 2*(pos-1)+1, otherwise 2*(pos-n/2) will give the required answer. Following is the C++ implementation.
This problem was originally appeared in Codeforces.