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 718●11●19●25 accept rate: 5%

 2 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 A(N); // the input array vector< vector > dp(N, vector(N,1)); vector< unordered_map > 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";  answered 06 Feb '14, 18:51 7★xellos0 5.9k●5●42●92 accept rate: 10% I did not get it please give me the exact code for it it will be helpful .thanks (07 Feb '14, 10:44) 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) 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★
 0 My solution takes O[N] time. N is the length of the array.  prev = A[0]; for(i=1;i
 toggle preview community wiki:
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:

×93
×40
×27

question asked: 06 Feb '14, 18:11

question was seen: 5,416 times

last updated: 09 Feb '14, 16:58