Sponsored
Sponsored
This approach uses dynamic programming and hashmaps to calculate arithmetic subsequences efficiently. For each index, we maintain a hashmap that tracks the count of different differences (arithmetic differences) and the number of subsequences that end with that difference at the given index. This allows us to build potential subsequences as we iterate over the array.
Time Complexity: O(n^2), where n is the length of the input array.
Space Complexity: O(n * m), where m is the number of possible differences (limited by the constraint of 31-bit integer).
1from collections import defaultdict
2
3def numberOfArithmeticSlices(nums):
4 total, n = 0, len(nums)
5 dp = [defaultdict(int) for _ in range(n)]
6
7 for i in range(n):
8 for j in range(i):
9 diff = nums[i] - nums[j]
10 count_at_j = dp[j][diff]
11 dp[i][diff] += count_at_j + 1
12 total += count_at_j
13 return total
14
15# Test
16nums = [2, 4, 6, 8, 10]
17print(numberOfArithmeticSlices(nums))This Python solution uses `defaultdict` to automatically handle key presence in the dictionary for differences. The outer loop iterates over `i` and the inner loop computes over all previous indices `j`, forming differences and updating the counts.
This approach considers all possible subsequences (using combinations) and checks if each subsequence is arithmetic. Although not efficient, it can be used to demonstrate the logic on small arrays to understand the problem better.
Time Complexity: O(n * 2^n) for combinations, where n is length of `nums`.
Space Complexity: O(n) given additional space for combinations.
1using System.Collections.Generic;
class ArithmeticSlicesBrute {
private bool IsArithmetic(List<int> seq) {
if (seq.Count < 3) return false;
int diff = seq[1] - seq[0];
for (int i = 2; i < seq.Count; i++) {
if (seq[i] - seq[i - 1] != diff)
return false;
}
return true;
}
private void GenerateSubsequences(int[] nums, List<int> curr, int start, ref int total) {
if (curr.Count >= 3 && IsArithmetic(curr)) {
total++;
}
for (int i = start; i < nums.Length; i++) {
curr.Add(nums[i]);
GenerateSubsequences(nums, curr, i + 1, ref total);
curr.RemoveAt(curr.Count - 1);
}
}
public int NumberOfArithmeticSlices(int[] nums) {
List<int> curr = new List<int>();
int total = 0;
GenerateSubsequences(nums, curr, 0, ref total);
return total;
}
static void Main() {
int[] nums = {2, 4, 6, 8, 10};
ArithmeticSlicesBrute asb = new ArithmeticSlicesBrute();
Console.WriteLine(asb.NumberOfArithmeticSlices(nums));
}
}This C# solution following a similar pattern of brute force, iteratively builds every possible subsequence, checks for the arithmetic conditions, and keeps a cumulative count. While simple for understanding, it's resource-intensive for anything beyond trivial sets of data.