# Solution For Arithmetic Slices Ii Subsequence

Arithmetic Slices II – Subsequence problem can be solved using dynamic programming approach. The problem statement describes that we have to find the number of arithmetic subsequence which have a length of at least 3. An arithmetic sequence is a sequence where the difference between two consecutive elements is the same throughout the sequence. For example, 1, 3, 5, 7 is an arithmetic sequence with a common difference of 2.

To solve this problem, we will use dynamic programming to build a table of counts. The table will keep track of the number of arithmetic subsequences that end at each position in the input array. We choose this because when we add an element to the table, we can check if it can extend any previous subsequences.

Algorithm:

- Create a dictionary dp with default value 0 to keep track of the counts of arithmetic subsequences.
- Loop through the input array, for each element a[i]:

a. Loop through the array from 0 to i-1, for each element a[j]:

i. Calculate the arithmetic difference between a[i] and a[j]: diff = a[i] – a[j] ii. Check if the dictionary dp already has a key (i, diff) then increment the value by dp[(j, diff)] iii. Increment dp[(i, diff)] by dp[(j, diff)] + 1 - In the above step, we are calculating the count of arithmetic subsequences ending at position i whose last element has a difference diff with element i and we do this by looping over all the indices j less than i and forming a valid arithmetic subsequence ending at j with difference diff and calculate the value dp[j, diff] for them. Now, we can extend all these subsequences by adding i itself as the next element in them thus we increment dp[i, diff] by value of dp[j, diff] +1 for all such subsequences.
- Finally loop through the dictionary dp, summing all the values >=3. This will give us the total count of arithmetic subsequences of length >=3.

Let’s implement it in Python:

`def numberOfArithmeticSlices(nums):`

dp = {}

for i in range(len(nums)):

for j in range(i):

diff = nums[i] - nums[j]
if (j, diff) in dp:

dp[(i, diff)] = dp[(j, diff)] + dp.get((i, diff), 0)

dp[(i, diff)] = dp.get((i, diff), 0) + 1

count = 0

for key in dp:

if dp[key] >= 3:

count += dp[key]
return count

Time Complexity:

The nested loops run n^2 times, so the time complexity is O(n^2).

Space Complexity:

We are using a dictionary to store the dp table with a maximum size of n^2, so the space complexity is O(n^2).

Overall, this is a very efficient and optimal solution for the given problem.

## Step by Step Implementation For Arithmetic Slices Ii Subsequence

class Solution { public int numberOfArithmeticSlices(int[] A) { // edge case if (A == null || A.length < 3) { return 0; } // dp[i] represents the number of arithmetic subsequences of A[i] int[] dp = new int[A.length]; // map stores all the differences with its corresponding counts // for example, if A[i] - A[j] = 0, then we have dp[i] * (dp[j] - 1) arithmetic subsequences Map[] map = new HashMap[A.length]; for (int i = 0; i < A.length; i++) { map[i] = new HashMap<>(); // we only need to consider the elements before A[i] for (int j = 0; j < i; j++) { // to avoid duplicate, we only need to consider j > 0 if ((long)A[i] - A[j] > Integer.MAX_VALUE || (long)A[i] - A[j] < Integer.MIN_VALUE) { continue; } int diff = A[i] - A[j]; int prev = map[j].getOrDefault(diff, 0); int curr = map[i].getOrDefault(diff, 0); // update dp[i] and map dp[i] += prev; map[i].put(diff, prev + curr + 1); } } int res = 0; for (int num : dp) { res += num; } return res; } }

def numberOfArithmeticSlices(A): # Write your code here res = 0 n = len(A) dp = [collections.defaultdict(int) for i in range(n)] for i in range(1, n): for j in range(i): diff = A[i] - A[j] dp[i][diff] += 1 if diff in dp[j]: dp[i][diff] += dp[j][diff] res += dp[j][diff] return res

var numberOfArithmeticSlices = function(A) { var len = A.length, dp = [], res = 0; for (var i = 0; i < len; i++) { dp[i] = []; for (var j = 0; j < i; j++) { var diff = A[i] - A[j]; if (dp[j][diff] !== undefined) { // if there is a same diff value before dp[i][diff] = (dp[i][diff] || 0) + dp[j][diff]; res += dp[j][diff]; } else { dp[i][diff] = 2; // update the dp value } } } return res; };

class Solution { public: int numberOfArithmeticSlices(vector& A) { // this problem is similar to problem 413, // but with one difference: // we need to take into account all possible subsequences, // not only those that are consecutive int n = A.size(); int res = 0; // dp[i][diff] represents the number of arithmetic subsequences // with A[i] as the last element and difference diff unordered_map dp[n]; for (int i = 0; i < n; ++i) { for (int j = 0; j < i; ++j) { // calculate the difference between A[i] and A[j] long diff = (long)A[i] - (long)A[j]; // if the difference is not within the range of an int, // then we can't have an arithmetic subsequence if (diff > INT_MAX || diff < INT_MIN) continue; // otherwise, we can have an arithmetic subsequence dp[i][diff] += 1; // we also need to add the number of arithmetic subsequences // that end with A[j] and have the same difference if (dp[j].count(diff)) dp[i][diff] += dp[j][diff]; // update the total number of arithmetic subsequences res += dp[j][diff]; } } return res; } };

public class Solution { public int NumberOfArithmeticSlices(int[] A) { // edge case if(A.Length < 3){ return 0; } // initializing our hashmap to store the number of times we've seen a given difference // between two numbers occur Dictionary[] map = new Dictionary [A.Length]; for(int i = 0; i < A.Length; i++){ map[i] = new Dictionary (); } // initializing our variable to keep track of the total number of arithmetic subsequences int result = 0; // iterating through the array for(int i = 1; i < A.Length-1; i++){ // iterating through all the numbers before the current number for(int j = 0; j < i; j++){ // calculating the difference between the current number and the number at index j long diff = (long)A[i] - (long)A[j]; // if the difference is not within the range of an int, we can't have a valid arithmetic subsequence // so we move on to the next number if(diff > int.MaxValue || diff < int.MinValue){ continue; } // if we've seen this difference before, we update our count of arithmetic subsequences // by adding the number of times we've seen this difference before to our current count if(map[j].ContainsKey((int)diff)){ result += map[j][(int)diff]; } // updating the number of times we've seen this difference at our current index if(!map[i].ContainsKey((int)diff)){ map[i].Add((int)diff, 0); } map[i][(int)diff]++; } } // returning the total number of arithmetic subsequences return result; } }