## February LeetCoding Challenge 2021

Day 18

## ARITHMETIC SLICES

**PROBLEM STATEMENT:**

1, 3, 5, 7, 9 7, 7, 7, 7 3, -1, -5, -9The following sequence is not arithmetic.

1, 1, 2, 5, 7

A zero-indexed array A consisting of N numbers is given. A slice of that array is any pair of integers (P, Q) such that 0 <= P < Q < N.

A slice (P, Q) of the array A is called arithmetic if the sequence:
A[P], A[P + 1], …, A[Q – 1], A[Q] is arithmetic. In particular, this means that P + 1 < Q.

The function should return the number of arithmetic slices in the array A.

**Example**

A = [1, 2, 3, 4] return: 3, for 3 arithmetic slices in A: [1, 2, 3], [2, 3, 4] and [1, 2, 3, 4] itself.

## Explanation

Every consecutive number in an arithmetic sequence has a common difference. For an arithmetic sequence of length

`N`

there will be 1 sub sequence of length N, 2 sub sequence of length N-1 and so on upto N-2 sub sequence of length 3, that is also arithmetic. Therefore total number of sequence that is arithmetic will be *1+2+3...+N-2 = [(N-2)*(N-2+1)]/2*

(some of N-2 natural numbers). So we need to find the length of all the sequences inside the given array that is arithmetic and use the above formula to find the final result.**ALGORITHM: **

- Initialize two pointers left=0 and right=1 that keeps track of the start and the end index of the current arithmetic sequence, and a variable

that keeps track of its common difference.*d* - Move the right pointer over the array from index 1 to last.
- If the diffrence of the current element and previous element is not equal to the current common diffrence that means we have reached the end of current arithmetic sequence.
- Find the total number of sub sequence present using the above derived formula and add it to the result.
- Update left with right – 1 and the common diffrence with the new common diffrence.

- Time complexity : O(n)
- Space Complexity : O(1)

## code

## C++

```
class Solution {
public:
int find_total(int n){
n = n-2;
return (n*(n+1))/2;
}
int numberOfArithmeticSlices(vector<int>& A) {
if(A.size()<2) return 0;
int res = 0;
int d = A[1]-A[0];
int left = 0;
int right;
for(right=1;right<A.size();++right){
if(A[right]-A[right-1] != d){
res += find_total(right-left);
d = A[right]-A[right-1];
left = right-1;
}
}
return res+find_total(right-left);
}
};
```

## PYTHON

```
class Solution:
def find_total(self,n: int) -> int:
n = n-2
return (n*(n+1))/2
def numberOfArithmeticSlices(self, A: List[int]) -> int:
if len(A) < 2:
return 0
res = 0
right = 1
left = 0
d = A[1]-A[0]
for right in range(1,len(A)):
if A[right]-A[right-1] != d:
res += self.find_total(right-left)
d = A[right]-A[right-1]
left = right - 1
res += self.find_total(right-left+1)
return int(res);
```