# Math problem O(N) solution IF given A[i] itself is arithmetic

• Note: this is NOT a solution to the original problem, only a reduced case.

Initially I misunderstood the problem by taking the given `vector<int> A` itself as an arithmetic array, which is only a reduced case of the original problem. However, I think the reduced case is still an interesting problem since it becomes a math problem with O(N) solution.

If `vector<int> A` itself is an arithmetic array, the problem will have nothing to do with the values but only the indices. For edge case when `vector<int> A` is a constant array, obviously it has n-2 distinct sub arithmetic arrays. Now we consider the non-trivial case.

Note that a sub arithmetic array is uniquely determined by its initial index i and common index difference d. Then we have length of longest sub arithmetic array starting from index i with common index difference d is

• L(i, d) = [(n-1-i)/d] + 1 ("[ ]" is the floor function),

then the count of all distinct sub arithmetic arrays is

• Count = Σi, d (L(i, d) - 2), sum only for those L(i, d) ≥ 3.

The range is 0 ≤ i ≤ n-1-2d, so

• Count = Σd=1:[(n-1)/2]i=2d:n-1 ([i/d]-1)}
= Σd=1:[(n-1)/2] { d(2+3+...+(q-1)) + q(r+1) - (n-2d) }
= Σd=1:[(n-1)/2] { d(q+1)(q-2)/2 + q(r+1) - (n-2d) },

where q = [(n-1)/d] and r = (n-1)%d.

``````    int numberOfArithmeticSlices(vector<int>& A) {
int n = A.size(), res = 0;
if (n < 3) return 0; else if (A[0] == A[1]) return n - 2;
for (int d = 1; d <= (n-1)/2; ++d) {
int q = (n-1)/d, r = (n-1)%d;
res += (d*(q-2)*(q+1)/2 + (r+1)*q - n + 2*d);
}
return res;

``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.