Arithmetic Subarrays
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

Question

Arithmetic Subarrays

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

Accepted Answer

Count the number of arithmetic subarrays in an array.

An arithmetic subarray has 3 or more elements with the same difference between consecutive elements.
Loop through the array and check for all possible subarrays with 3 or more elements.
If the difference between consecutive elements is the same, increment the count.
Return the count for each test case.

Accepted Answer

We use a vector of unordered_maps for our dynamic programming.
The vector is used as follows: [ index, {diff, count} ].
For each index, we have all common differences and count arithmetic slices up to that index.

We iterate through the given vector nums, and for each number we iterate again from the beginning to there.
diff is the difference, so we can add 1 to the counter of dp[i][diff].
If we already have a key for diff in dp[j], we can add to dp[i][diff] all the count that we had by dp[j][diff]. And that's what we add to our res.

Accepted Answer

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

Space Complexity: O(1)Explanation:

O(1)

No additional memory is being used.

Time Complexity: O(n^2)Explanation:

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)

Python (3.5)

"""

    Time Complexity: O(N ^ 2)

    Space Complexity: O(1)

    

    Where N is length of the array.

"""



def arithmeticSubarrays(a, n) :

    res = 0



    for i in range(n-2):

        d = a[i + 1] - a[i]



        for j in range(i+2,n):

            if (a[j] - a[j - 1] == d) :

                # Subarray i...j  is an arithmatic subarray

                res+=1

            else :

                break

                

    return res

C++ (g++ 5.4)

/*

    Time Complexity: O(N ^ 2)

    Space Complexity: O(1)

 

    Where N is length of the array

*/



int arithmeticSubarrays(vector &a, int n)

{

    int res = 0;



    for (int i = 0; i < n - 2; i++)

    {

        int d = a[i + 1] - a[i];



        for (int j = i + 2; j < n; j++)

        {

            if (a[j] - a[j - 1] == d)

            {

 

                // Subarray i...j  is an arithmatic subarray

                res++;

            }

            else

            {

                break;

            }

        }



    }

    return res;

}

Java (SE 1.8)

/*

    Time Complexity: O(N ^ 2)

    Space Complexity: O(1)

    

    Where N is length of the array.

*/



public class Solution 

{

    public static int arithmeticSubarrays(int[] arr, int n) 

    {

        int res = 0;



        for (int i = 0; i < n - 2; i++) 

        {

            int d = arr[i + 1] - arr[i];



            for (int j = i + 2; j < n; j++) 

            {

                if (arr[j] - arr[j - 1] == d) 

                {



                    // Subarray i...j  is an arithmatic subarray

                    res++;

                } 

                else 

                {

                    break;

                }

            }



        }

        return res;

    }

}

Accepted Answer

Counting arithmetic subarrays

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

Space Complexity: O(1)Explanation:

O(1)

No additional memory is being used.

Time Complexity: O(n)Explanation:

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

We are only iterating over the array ‘A’ of length N, thus complexity is O(N).

C++ (g++ 5.4)

/*

    Time Complexity: O(N)

    Space Complexity: O(1)

 

    Where N is length of the array.

*/



int arithmeticSubarrays(vector &a, int n)

{

    int k = 0, res = 0;



    for (int i = 2; i < n; i++)

    {

 

        // Check if we have 3 consecutive elements have same difference.

        if ( a[i] - a[i - 1] == a[i - 1] - a[i - 2] )

        {

            k++;

        }

        else

        {

 

            // 'k' is the maximum number of arithmetic subarray in previous slice.

            res += k * (k + 1) / 2;

            k = 0;

        }

    }



    res += k * (k + 1) / 2;



    return res;

}

Python (3.5)

"""

    Time Complexity: O(N)

    Space Complexity: O(1)



    Where N is length of the array

"""



def arithmeticSubarrays(a,n) :

	k=0

	res=0



	for i in range(2,n) :



        # Check if we have 3 consecutive elements have same difference.

		if ( a[i] - a[i - 1] == a[i - 1] - a[i - 2] ) :

			k+=1

		else :

            

			# 'k' is the maximum number of arithmetic subarray in previous slice.

			res += k * (k + 1) // 2

			k = 0

		

	



	res += k * (k + 1) // 2



	return res

Java (SE 1.8)

/*

    Time Complexity: O(N)

    Space Complexity: O(1)

    

    Where N is length of the array.

*/



public class Solution 

{

    public static int arithmeticSubarrays(int[] arr, int n) 

    {

        int k = 0, res = 0;



        for (int i = 2; i < n; i++) 

        {  

     

            // Check if we have 3 consecutive elements have same difference.

            if ( arr[i] - arr[i - 1] == arr[i - 1] - arr[i - 2] ) 

            {

                k++;

            } 

            else 

            {

     

                // 'k' is the maximum number of arithmetic subarray in previous slice.

                res += k * (k + 1) / 2;

                k = 0;

            }

        }



        res += k * (k + 1) / 2;



        return res;

    }

}

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:

Input Format:

Output Format:

Note:

Constraints:

Top Dunzo Software Developer interview questions & answers

Popular interview questions of Software Developer