Number of arithmetic progression subsequences in a given set of numbers

Given an array of n positive integers. The task is to count the number of Arithmetic Progression subsequence in the array.

Arithmetic Progression is defined as a series of a, a + d, a + 2 * d, etc.
By difference of Arithmetic Progression we mean d.

Let us look at few of Examples:-

 Input : arr[] = { 1, 2, 3 }
 Output : 8
 Arithmetic Progression subsequence from the 
 given array are: {}, { 1 }, { 2 }, { 3 }, { 1, 2 },
 { 2, 3 }, { 1, 3 }, { 1, 2, 3 }.

 Input : arr[] = { 10, 20, 30, 45 }
 Output : 12

 Input : arr[] = { 1, 2, 3, 4, 5 }
 Output : 23

Note: 1.Empty sequence or single element sequence is Arithmetic Progression.
2.we have considered A[i] in range 1 to 1000000(inclusive).

Since empty sequence and single element sequence is also arithmetic progression, so we initialize the answer with n(number of element in the array) + 1.

Now, we need to find the arithmetic progression subsequence of length greater than or equal to 2. Let minimum and maximum of the array be minarr and maxarr respectively. Observe, in all the arithmetic progression subsequences, the range of common difference will be from (minarr – maxarr) to (maxarr – minarr).

We will solve this problem by dynamic programming. Let dp[i] denote the number of AP's ending at i and having difference equal to d. So if our current number is equal to A[i], we need to find all the positions j < i such that A[j] = A[i] - diff and we will take sum of dp[j] for those j's. It is equivalent to extending the APs ending at position j with the element at position i.

Hence dp[i] = sum_(j = 1 to i - 1) dp[j] such that A[j] = A[i] - diff

we can optimize this by maintaining a sum array where sum[x] will record sum of all the dp's where the value of array elements was x.

    sum[x] = sum of all dp[i]'s such that A[i] = x.

After this, our dp will be.

  Hence dp[i] = sum[A[i] - diff] + 1.

Now with this optimization, our dp computation will take O(N) time.

Complexity

Time complexity: O(n)

Implementation

Let us look at Dynamic programming approach:-

#include<bits/stdc++.h> 
#define MAX 1000001 
using namespace std; 
int numofAP(int a[], int n) 
{ 
    // initializing the minimum value and 
    // maximum value of the array. 
    int minarr = INT_MAX, maxarr = INT_MIN; 
    // Finding the minimum and maximum 
    // value of the array. 
    for (int i = 0; i < n; i++) 
    { 
        minarr = min(minarr, a[i]); 
        maxarr = max(maxarr, a[i]); 
    } 
    // dp[i] is going to store count of APs ending 
    // with arr[i]. 
    // sum[j] is going to store sun of all dp[]'s 
    // with j as an AP element. 
    int dp[n], sum[MAX]; 
    // Initialize answer with n + 1 as single elements 
    // and empty array are also DP. 
    int ans = n + 1; 
    // Traversing with all common difference. 
    for (int d=(minarr-maxarr); d<=(maxarr-minarr); d++) 
    { 
        memset(sum, 0, sizeof sum); 
        // Traversing all the element of the array. 
        for (int i = 0; i < n; i++) 
        { 
            // Initialize dp[i] = 1. 
            dp[i] = 1; 
            // Adding counts of APs with given differences 
            // and a[i] is last element.   
            // We consider all APs where an array element 
            // is previous element of AP with a particular  
            // difference 
            if (a[i] - d >= 1 && a[i] - d <= 1000000) 
                dp[i] += sum[a[i] - d]; 
            ans += dp[i] - 1; 
            sum[a[i]] += dp[i]; 
        } 
    } 
    return ans; 
} 
// Driver code 
int main() 
{ 
    int arr[] = { 1, 2, 3 }; 
    int n = sizeof(arr)/sizeof(arr[0]); 
    cout << numofAP(arr, n) << endl; 
    return 0; 
}
  

Output:
8