Arithmetic Subarrays

Easy
0/40
Average time to solve is 20m
profile
Contributed by
11 upvotes
Asked in companies
HCL TechnologiesDunzoAmazon

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
4
1 3 5 7
2
1 2
Sample Output 1:
3
0
Explanation For Sample Input 1:
In test case 1:

We have A = [1 3 5 7]
Diff of consecutive elements: 
A[1]- A[0] = 3-1 = 2
A[2]- A[1] = 5-3 = 2
A[3]- A[2] = 7-5 = 2

[1 3 5], [3 5 7], and [1 3 5 7] are the three arithmetic subarray.
Thus the answer is 3.

In test case 2:

We have A = [1 2]
The length of the array is 2, which means that there can be no subarray of length 3 or more.
Thus the number of arithmetic subarrays is 0.
Sample Input 2:
2
9
9 3 52 46 40 34 8 7 6 
5
4 19 34 49 35
Sample Output 2:
4
3
Hint

Check all subarrays whether they are arithmetic or not.

Approaches (2)
Brute Force

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’.
Time Complexity

O(N ^ 2),  where N is the length of the array

 

We are using nested loops both have O(N) complexity, thus the time complexity of the program is O(N ^ 2)

Space Complexity

O(1)

 

No additional memory is being used.

Code Solution
(100% EXP penalty)
Arithmetic Subarrays
Full screen
Console