You are not logged in. Please login at www.codechef.com to post your questions!

×

Arithmetic series -Google Interview Question

1
1

Given an array of integers A, give an algorithm to find the longest Arithmetic progression in it, i.e find a sequence i1 < i2 < … < ik, such that A[i1], A[i2], …, A[ik] forms an arithmetic progression, and k is the largest possible length.

The sequence S1, S2, …, Sk is called an arithmetic progression if Sj+1 – Sj is a constant.

asked 06 Feb '14, 18:11

theshubhamgoel's gravatar image

3★theshubhamgoel
718111925
accept rate: 5%


I have an O(N^2) solution with DP.

Let dp[i][j] be the answer, if our progression ends with the j-th and i-th element (j <= i; dp[i][i] == 1). Let X[i] be a hash-table (or just an array, if A[i] are small enough, or a map<> if you don't want a hash table, for an additional O(log N) factor to the complexity), in which you store pairs (A[i]-A[j],j) for j < i; in case of a tie in A[i]-A[j], just the larger j. This table can be constructed easily from dp[i] in linear time.

What happens when you want to know dp[i][j]? It's just a progression ending with the j-th element, and you append the i-th element, so dp[i][j] == 1+dp[k][j]. The index k is the largest index (<= j) for which A[j]-A[k] == A[i]-A[j], so it's the second part of the entry (A[i]-A[j],k) in X[j]. If that entry doesn't exist, then dp[i][j] == 2. Thanks to the hash-table, we can find dp[i][j] in O(1), so we have O(N^2) total complexity.

I find it hard to believe that there could be an algorithm in O(N log N) (note that O-notation means "or better"), so this'll have to do...

Code (includes excluded :D)

int N, ans =1;
vector<int> A(N); // the input array
vector< vector<int> > dp(N, vector<int>(N,1));
vector< unordered_map<int,int> > X(N);

for(int i =0; i < N; i++) {
    for(int j =0; j < i; j++) {
        if(X[j].find(A[i]-A[j]) == X[j].end()) {
            dp[i][j] =2;
            continue;}
        int k =X[j][A[i]-A[j]];
        dp[i][j] =max(dp[i][j],dp[j][k]+1);}
    for(int j =0; j < i; j++) {
        X[i][A[i]-A[j]] =j;
        ans =max(ans,dp[i][j]);}
    }
cout << ans << "\n";
link

answered 06 Feb '14, 18:51

xellos0's gravatar image

7★xellos0
5.9k54191
accept rate: 10%

edited 07 Feb '14, 16:55

I did not get it please give me the exact code for it it will be helpful .thanks

(07 Feb '14, 10:44) theshubhamgoel3★

Really? You need a code for DP, which is almost always just about re-writing the formulas mentioned? sigh Ok, I'll do it.

(07 Feb '14, 15:31) xellos07★

hey xellos0 can u give the reference for DP as I am not comfortable with DP. Thanks

(08 Feb '14, 19:04) theshubhamgoel3★
1

Sorry, no. I learn to solve problems by solving problems, not by doing theory. But you could do the same and use this problem as a basic idea about how DP works.

(08 Feb '14, 19:54) xellos07★

My solution takes O[N] time. N is the length of the array.

    prev = A[0];
    for(i=1;i<N;i++)
    {
        A[i] = A[i]-prev;
        prev = A[i];
    }

A[0] = A[1];
A[N] = A[N-1];

Now just find indexs i and j such that all elements A[i] to A[j] are equal and j-i is maximum. This can be done In O[N] time

link

answered 08 Feb '14, 21:38

krats's gravatar image

3★krats
153
accept rate: 0%

edited 08 Feb '14, 21:40

5

Then I advise you to read the question again. It asks for an arithmetic subsequence, not substring.

(08 Feb '14, 23:35) xellos07★

Then i suggest you try and understand my answer before criticising it. What i am doing above is changing the elements in the array such that each element is the difference between itself and the previous element. Now all you need to do is find the sub array with maximum number of elements which are consecutive and equal. If you need to return the sub array instead of the indexes i and j referring to start and end position of the subarray then i suggest you store the first element of the array in a variable . Using this variable you can get back the previous array . All this takes O[N] time.

(09 Feb '14, 15:39) krats3★
1

Consecutive equal elements means substring. We don't want consecutive. And I wasn't talking about what we need to return, at all.

(09 Feb '14, 16:54) xellos07★

ya you are right . I thought we have to find consecutive elements.

(09 Feb '14, 16:58) krats3★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×60
×40
×27

question asked: 06 Feb '14, 18:11

question was seen: 5,388 times

last updated: 09 Feb '14, 16:58