Example:
For simplicity, we have assumed that the given set is sorted. We can always add a pre-processing step to first sort the set and then apply the below algorithms.
A simple solution is to one by one consider every pair as first two elements of AP and check for the remaining elements in sorted set. To consider all pairs as first two elements, we need to run a O(n^2) nested loop. Inside the nested loops, we need a third loop which linearly looks for the more elements in Arithmetic Progression (AP). This process takes O(n3) time.
Dynamic Programming algorithm:
Refer the paper http://www.cs.uiuc.edu/~jeffe/pubs/pdf/arith.pdf
Let us first look at
Given a sorted set, find if there exist three elements in Arithmetic Progression or not
algorithm-
The answer is true if there are 3 or more elements in AP, otherwise false.
To find the three elements, we first fix an element as middle element and search for other two (one smaller and one greater). We start from the second element and fix every element as middle element. For an element set[j] to be middle of AP, there must exist elements ‘set[i]‘ and ‘set[k]‘ such that set[i] + set[k] = 2*set[j] where 0 <= i < j and j < k <=n-1.
How to efficiently find i and k for a given j? We can find i and k in linear time using following simple algorithm.
1) Initialize i as j-1 and k as j+1
2) Do following while i >= 0 and j <= n-1
..........a) If set[i] + set[k] is equal to 2*set[j], then we are done.
……..b) If set[i] + set[k] > 2*set[j], then decrement i (do i–-).
……..c) Else if set[i] + set[k] < 2*set[j], then increment k (do k++).
Program:
#include <iostream>
using namespace std;
// The function returns true if there exist three elements in AP
// Assumption: set[0..n-1] is sorted
bool arithmeticThree(int set[], int n)
{
// One by fix every element as middle element
for (int j=1; j<n-1; j++)
{
// Initialize i and k for the current j
int i = j-1, k = j+1;
// Find if there exist i and k that form AP
// with j as middle element
while (i >= 0 && k <= n-1)
{
if (set[i] + set[k] == 2*set[j])
return true;
(set[i] + set[k] < 2*set[j])? k++ : i--;
}
}
return false;
}
int main()
{
int set1[] = {1, 7, 10, 15, 27, 29};
int n1 = sizeof(set1)/sizeof(set1[0]);
arithmeticThree(set1, n1)? cout << "Yes\n" : cout << "No\n";
int set2[] = {1, 7, 10, 15, 27, 28};
int n2 = sizeof(set2)/sizeof(set2[0]);
arithmeticThree(set2, n2)? cout << "Yes\n" : cout << "No\n";
return 0;
}
How to extend the above solution for the original problem? algorithm-
If the given set has two or more elements, then the value of LLAP is at least 2.The idea is to create a 2D table L[n][n]. An entry L[i][j] in this table stores LLAP with set[i] and set[j] as first two elements of AP and j > i. The last column of the table is always 2. Rest of the table is filled from bottom right to top left. To fill rest of the table, j (second element in AP) is first fixed. i and k are searched for a fixed j. If i and k are found such that i, j, k form an AP, then the value of L[i][j] is set as L[j][k] + 1. Note that the value of L[j][k] must have been filled before as the loop traverses from right to left columns.
Program:
Output:
Auxiliary Space: O(n2)
set[] = {1, 7, 10, 15, 27, 29} output = 3 The longest arithmetic progression is {1, 15, 29}
For simplicity, we have assumed that the given set is sorted. We can always add a pre-processing step to first sort the set and then apply the below algorithms.
A simple solution is to one by one consider every pair as first two elements of AP and check for the remaining elements in sorted set. To consider all pairs as first two elements, we need to run a O(n^2) nested loop. Inside the nested loops, we need a third loop which linearly looks for the more elements in Arithmetic Progression (AP). This process takes O(n3) time.
Dynamic Programming algorithm:
Refer the paper http://www.cs.uiuc.edu/~jeffe/pubs/pdf/arith.pdf
Let us first look at
Given a sorted set, find if there exist three elements in Arithmetic Progression or not
algorithm-
The answer is true if there are 3 or more elements in AP, otherwise false.
To find the three elements, we first fix an element as middle element and search for other two (one smaller and one greater). We start from the second element and fix every element as middle element. For an element set[j] to be middle of AP, there must exist elements ‘set[i]‘ and ‘set[k]‘ such that set[i] + set[k] = 2*set[j] where 0 <= i < j and j < k <=n-1.
How to efficiently find i and k for a given j? We can find i and k in linear time using following simple algorithm.
1) Initialize i as j-1 and k as j+1
2) Do following while i >= 0 and j <= n-1
..........a) If set[i] + set[k] is equal to 2*set[j], then we are done.
……..b) If set[i] + set[k] > 2*set[j], then decrement i (do i–-).
……..c) Else if set[i] + set[k] < 2*set[j], then increment k (do k++).
Program:
#include <iostream>
using namespace std;
// The function returns true if there exist three elements in AP
// Assumption: set[0..n-1] is sorted
bool arithmeticThree(int set[], int n)
{
// One by fix every element as middle element
for (int j=1; j<n-1; j++)
{
// Initialize i and k for the current j
int i = j-1, k = j+1;
// Find if there exist i and k that form AP
// with j as middle element
while (i >= 0 && k <= n-1)
{
if (set[i] + set[k] == 2*set[j])
return true;
(set[i] + set[k] < 2*set[j])? k++ : i--;
}
}
return false;
}
int main()
{
int set1[] = {1, 7, 10, 15, 27, 29};
int n1 = sizeof(set1)/sizeof(set1[0]);
arithmeticThree(set1, n1)? cout << "Yes\n" : cout << "No\n";
int set2[] = {1, 7, 10, 15, 27, 28};
int n2 = sizeof(set2)/sizeof(set2[0]);
arithmeticThree(set2, n2)? cout << "Yes\n" : cout << "No\n";
return 0;
}
How to extend the above solution for the original problem? algorithm-
If the given set has two or more elements, then the value of LLAP is at least 2.The idea is to create a 2D table L[n][n]. An entry L[i][j] in this table stores LLAP with set[i] and set[j] as first two elements of AP and j > i. The last column of the table is always 2. Rest of the table is filled from bottom right to top left. To fill rest of the table, j (second element in AP) is first fixed. i and k are searched for a fixed j. If i and k are found such that i, j, k form an AP, then the value of L[i][j] is set as L[j][k] + 1. Note that the value of L[j][k] must have been filled before as the loop traverses from right to left columns.
Program:
// C++ program to find Length of the Longest AP (llap) in a given sorted set. |
4 3 5Time Complexity: O(n2)
Auxiliary Space: O(n2)
No comments:
Post a Comment