Tag Archives: codeforces

Finding the the number at a given position in even odd array

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.

Maximum increasing sub array

Given an array of numbers, how to find the maximum length of increasing (non-decreasing) continuous sub-sequence?

For example consider the array [7, 9, 1, 3, 5, 8, 2], the maximum length is 4. Similarly for [23, 10, 18, 18, 6], it is 3.

This is a straight forward implementation problem (appeared on Codeforces). Following is an implementation of O(n) algorithm.