Tell me more ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.
up vote 0 down vote favorite
1

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,25
AP: 2,4,6,8,10,12
GP: 4,10,25

I 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.

share|improve this question
Is that a homework or assignment question? Provide us with some details what have you tried so far!!!! – Maxood Dec 7 '12 at 10:58
The problem is ill-defined. Are you required to use all the given numbers? Is there a minimum length to each series? – tdammers Dec 7 '12 at 13:39
2  
Obviously a series is defined by at least two numbers. Is that in the rules? The empty set and a set with one element can be quite nice as a series. With the series 2,4,6,8,10,12,25, I would say that 2,4,6,10,12 and 25 is also a solution. If 25 isn't valid, pick any arbitrary number from the first set and add it to the second and voila!, another solution. – David Hammen Dec 7 '12 at 15:22
1  
Please don't cross post – ChrisF♦ Dec 9 '12 at 11:14
1  
Please be aware that this is part of a contest - codechef.com/DEC12/problems/ARIGEOM – ChrisF♦ Dec 9 '12 at 11:28
show 3 more comments

closed as off topic by World Engineer♦, Glenn Nelson, Walter, Tim Post♦, gnat Dec 10 '12 at 9:04

Questions on Programmers Stack Exchange are expected to relate to software development within the scope defined in the FAQ. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about closed questions here.

4 Answers

up vote 3 down vote accepted

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.

share|improve this answer
Good algorithm. Was getting some problem in finding gcd of double but somehow managed due to some constraints. Thanks – user1814037 Dec 11 '12 at 0:38
up vote 1 down vote

Let's assume a sequence must contain at least 2 numbers. Here is a more or less brute-force approach:

  • calculate the difference of each pair of numbers: this gives you a finite number of possible differences (lets call that number set D). One of that differences must be the constant difference of the AP

  • also, calculate the of ratio each pair of numbers: this gives you a finite number of possible ratios (lets call that number set R). One of that must be the constant ration of the GP

  • Choose each pair (d,r) out of D x R. Test if you can find an AP beeing a sub-sequence with constant diff d and and a GP sub-sequence with constant ratio r, so that the union of both sub-sequences form the original sequence.

For the last step, you have to consider that there may be more than one possible subsequence for a given d or r. However, you can do better than just generating all possible sub-sequences if you make use of that fact that at least one of the two sequences must contain the first of all numbers, and the second one must contain one of the numbers which is not contained within the other sub-sequence.

For instance, when using your example above, the set D will contain 2 (and some more numbers), and R will contain 2, 2.5, and some more numbers. Testing d=2, r=2, will lead to the AP 2,4,6,8,10,12, but the remaining number 25 is not part of a GP with at least two numbers and r=2 (neither 50 nor 12.5 is part of the given number set). However, when the next test is d=2, r=2.5, you will easily find the solution above.

share|improve this answer
That's an O(n^5) solution, maybe worse. There has to be something better. But it is a solution, so +1. – David Hammen Dec 7 '12 at 15:29
up vote 0 down vote

I would rather interpret your example as
AP: 2,4,6,8,10,12
GP: 25
as this is a valid interpretation as well and easier to find.

I'd first look at the first three integers. Let's call them a, b and c.

  • If b - a = c - b, you can assume that this is the step width of your arithmetic series, and the geometric series has not started yet.
  • If b/a = c/b, you can assume that this is the ratio of the geometric series, and that the arithmetic series has not started yet.
  • Independently of whether or not either of the above conditions are met (thanks to tmyklebu for pointing this out), you have several other valid hypotheses. You can assume that any two of the numbers form the beginning of one of the series, and the remaining element the beginning of the other series.

You could maintain a list of currently valid hypotheses as you proceed along the array. In the case of a hypothesis with only a single started sequence, you have to assume that the first number not belonging to that sequence is the beginning of the other sequence. If you have one sequence and the start of another sequence, you will likely encounter a number which is not part of the defined sequence. You can use that to define the remaining sequence.

You have to take some care. When you had a geometric series and find the second number not fitting that series, you know you have found two numbers belonging to the arithmetic series. But their difference might be a multiple of the step width. So you should iterate over all divisors of that difference, and check whether the intermediate values indicated by thas reduced step width are present in the geometric series. Only up to two elements of an arithmetic series can be part of a geometric series as well, so no need to check all divisors. It is enough to check for half and one-third of the width, and only if that number is an integer. A similar consideration has to be used to find the ratio of the geometric series, taking posisble duplicate elements into account. You have to check for the square root and cubic root of the fraction of the two defining numbers, and see whether these are rational as well and result in integers. Rounding might be an issue unless you have a data structure to represent rational numbers and do prime factor decomposition.

It might be that multiple step widths or ratios are consistent with the data so far. In that case, you should go with all of them, checking the remaining data to see whether they still hold. In the end, you either have a single valid hypothesis, or a set of hypotheses from which you can choose at will. If you want to, you could then check whether any of these series can be extended before the assumed first element, by reusing elements of the other series. This could be used to find 4 and 10 in the example of yours. But the answer should be valid even without this step.

share|improve this answer
If b-a = c-b, you can't necessarily assume that it's the common difference of the arithmetic progression. Consider 1 2 3 5 7 9 11 13 15 64; the common difference must be two. Likewise if b/a = c/b. – tmyklebu Dec 7 '12 at 15:07
@tmyklebu, you are right, I updated my answer. You should always keep track of all possible hypotheses, i.e. the mixed ones as well even when a pure one seems to fit the beginning. – MvG Dec 7 '12 at 15:14
up vote 0 down vote

You can try some method to find the longest arithmetic progression. Here is simple DP solution with quadratic complexity, and full pdf document contains clues to (theoretically) more effective method.

This method is applicable to geometric series to (checking A[i] + A[k] = 2*A[j] turns into A[i] * A[k] = A[j] * A[j] and so on..)

share|improve this answer
You don't necessarily want the longest arithmetic progression, though. Consider 2 4 6 8 16 32 64 128 200; you want the powers of two in the geometric progression and you want the arithmetic progression to be 6 200. – tmyklebu Dec 7 '12 at 15:09

Not the answer you're looking for? Browse other questions tagged or ask your own question.