Given an array of positive integers in increasing order. Separate them in two series, an arithmetic sequence and geometric sequence. The given array is such that a solution do exist.The union of numbers of the two sequence must be the given array.Both series can have common elements i.e. series need not to be disjoint.The ratio of the geometric series can be fractional.Example:Given series : 2,4,6,8,10,12,25AP: 2,4,6,8,10,12GP: 4,10,25I tried taking few examples but could not reach a general way. Even tried some graph implementation by introducing edges if they follow a particular sequence but could not reach solution.
Separating merged array of arithmetic and geometric series
math;sequence
You can do this in linear time.First, notice that a geometric progression is just an arithmetic progression in the elementwise logarithm of the sequence.  So we can think of having a sequence of pairs of numbers that we want to cover with a progression that is arithmetic in the first element and a progression that is arithmetic in the second element.Two of the first three elements must lie in the same progression.  Without loss of generality, I'll assume it's the arithmetic progression.  You can find, in linear time, the longest arithmetic sequence with the right beginning and common difference that is a subsequence of your input.  You do that and then you're left with a bunch of uncovered elements; say their logarithms are g_1, g_2, ..., g_k.Find the greatest common divisor of g_2-g_1, ..., g_k-g_1 --- I want the biggest real number d such that g_2-g_1, g_3-g_1, ..., g_k-g_1 can all be written as multiples of d.Then, if there is a geometric progression covering g_1, ..., g_k that is a subsequence of your input, there must be one with common ratio d.  All you need to do is check that g_1, g_1 * exp(d), g_1 * exp(2d), ..., g_k are all elements of your input, and you can do this in linear time.So you do the above six times (twice --- arithmetic and geometric --- for each of the three possible choices of first two), and the above takes linear time.