Last Updated: 13 Apr, 2021
Arithmetic Subarrays
Easy
Asked in companies
You are given an array ‘A’ of length ‘N’, you have to tell the number of arithmetic subarrays that exist in the array ‘A’.
An Arithmetic subarray is a subarray that has 3 or more elements and the difference between consecutive elements is the same. Eg: [1, 3, 5, 7] has a length of 4, and diff between any two consecutive elements is 2.
Note:
A subarray is a slice from a contiguous array (i.e., occupy consecutive positions) and inherently maintains the order of elements.
Input Format:
The first line of the input contains ‘T’ denoting the number of test cases.
The first line of each test case contains the three integers N, length of the array.
The second line of each test case contains N space-separated integers of the array A.
Output Format:
For each test case, return the number of arithmetic subarrays that can be formed.
Note:
Don't print anything it has already been taken care of. Just implement the given function
Constraints:
1 <= T <= 100
1 <= N <= 3000
0 <= A[i] <= 5000
Time Limit: 1 second
Approaches
Here we use a simple idea that if we have an arithmetic subarray A[i...j] of difference ’d’ between two consecutive elements, then to check if subarray A[i….j+1] is also arithmetic subarray of common difference ‘d’, all we need to check is if A[j+1]-A[j] == ‘d’.
Algorithm:
- Create an integer, ‘res’= 0.
- Iterate over ‘i’ in range 0...N-3:
- Create a variable ‘d’ = A[i+1]-A[i];
- Iterate over ‘j’ in range i+2…...N-1:
- If A[j]-A[j-1] == ‘d’, then it means we found another arithmetic subarray (i, j), thus increase ‘res’, i.e. ‘res’= ‘res’+1
- Else break out of the loop, as there is no point in continuing, as the common difference between the consecutive elements will be different for future subarrays (i, j).
- Return ‘res’.
- If our A= [1 2 3 4 5 7 9 11] then B= [ 0 0 1 2 3 0 1 2], where ‘B’ is an array that tells the number of subarrays ending at index ‘i’, and we can clearly see some pattern in this array.
- In subarray [1 2 3 4 5] common difference ‘d’ of elements is 1, and the total number of arithmetic subarrays that can be formed from it are = 1 + 2 + 3 ( from array ‘B’ ) = 3*(3+1)/2.
- Similarly, for subarray [5 7 9 11], ‘d’= 2, and the total number of arithmetic subarrays that can be formed from it are = 1 + 2 = 2*(2+1)/2.
- Knowing this what we can do is divide our array ‘A’ into multiple slices of subarrays that have the same common difference ‘d’, such that these slices cannot be extended to retain ‘d’.
- Then the total number of arithmetic subarrays will be the sum of arithmetic subarrays of these slices.
- If ‘k’ is the maximum number of arithmetic subarrays that can be formed ending at index ‘i’ in the slice, then for the slice total number of arithmetic subarrays will be k * (k + 1) / 2.
Algorithm:
- Create two variables ‘k’= 0, and ‘res’=0.
- Iterate over i = 2...N - 1:
- If A[i]- A[i-1] == A[i-1] -A[i-2], i.e. we have 3 consecutive elements have same difference. Then increment ‘k’, i.e. ‘k’= ‘k’ +1.
- Else it means that currently a slice has ended with the same common difference and the maximum number of arithmetic subarrays that can be formed in it is ‘k’. Thus the total number of arithmetic subarrays = k*(k+1)/2, then increase ‘res’ by k*(k+1)/2 i.e. ‘res’ = ‘res’ + k*(k+1)/2 and set ‘k’=0 for the next slice.
- The last slice is never counted in ‘res’, thus we will increment the number of arithmetic subarrays for it. ‘res’ = ‘res’ + k*(k+1)/2
- Return ‘res’.