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).
1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4
5#define MAX_DIFF 20000
6#define OFFSET 10000
7
8int numberOfArithmeticSlices(int* nums, int numsSize) {
9 int res = 0;
10 int dp[numsSize][MAX_DIFF] = {0};
11
12 for (int i = 1; i < numsSize; i++) {
13 for (int j = 0; j < i; j++) {
14 long diff = (long)nums[i] - (long)nums[j] + OFFSET;
15 int count_at_j = dp[j][diff];
16 dp[i][diff] += count_at_j + 1;
17 res += count_at_j;
18 }
19 }
20 return res;
21}
22
23int main() {
24 int nums[] = {2, 4, 6, 8, 10};
25 int numsSize = sizeof(nums) / sizeof(nums[0]);
26 int result = numberOfArithmeticSlices(nums, numsSize);
27 printf("%d\n", result);
28 return 0;
29}This C solution involves using a 2D array `dp` where `dp[i][d]` represents the number of arithmetic subsequences ending at index `i` with common difference `d`. We iterate through pairs `(i, j)` where `j < i` and calculate the difference `d`. For each pair, we update the `dp` array and accumulate the answer in `res` by adding the count of subsequences ending at `j` with difference `d`.
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.
1#include <vector>
#include <cmath>
using namespace std;
bool isArithmetic(vector<int>& seq) {
if (seq.size() < 3) return false;
int diff = seq[1] - seq[0];
for (size_t i = 2; i < seq.size(); i++) {
if (seq[i] - seq[i - 1] != diff)
return false;
}
return true;
}
void generateSubsequences(vector<int>& nums, vector<int>& curr, int start, int& total) {
if (curr.size() >= 3 && isArithmetic(curr)) {
total++;
}
for (size_t i = start; i < nums.size(); i++) {
curr.push_back(nums[i]);
generateSubsequences(nums, curr, i + 1, total);
curr.pop_back();
}
}
int numberOfArithmeticSlices(vector<int>& nums) {
vector<int> curr;
int total = 0;
generateSubsequences(nums, curr, 0, total);
return total;
}
int main() {
vector<int> nums = {2, 4, 6, 8, 10};
cout << numberOfArithmeticSlices(nums) << endl;
return 0;
}C++ code creates all subsequences, calculates differences, and checks arithmetic properties, similar to the logic of permutating indices for combination generation. Despite being simple, its factorial growth in subsequences makes it impractical for larger inputs.