Arithmetic Slices | February Leetcoding Challenge 2021 | Day 18
logo
Manas Sinha
Developer | Designer

By Manas | 18 February 2021

February LeetCoding Challenge 2021

Day 18

ARITHMETIC SLICES

PROBLEM  STATEMENT:
A sequence of numbers is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same. For example, these are arithmetic sequences:
1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9
The 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 d that keeps track of its common difference.
  • 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);
                           

LEAVE A COMMENT

If you like the post leave a comment and share it.

Leave a Reply