Count the Arithmetic sequences in the Array of size at least 3

0 0 5 minutes read

Given an array arr[] of size N, the task is to find the count of all arithmetic sequences in the array.

Examples:

Input: arr = [1, 2, 3, 4]
Output: 3
Explanation:
The arithmetic sequences in arr are [1, 2, 3], [2, 3, 4] and [1, 2, 3, 4] itself.

Input: arr = [1, 3, 5, 6, 7, 8]
Output: 4
Explanation:
The arithmetic sequences in arr are [1, 3, 5], [5, 6, 7], [5, 6, 7, 8] and [6, 7, 8].

Naive approach:

Run two loops and check for each sequence of length at least 3.
If the sequence is an arithmetic sequence, then increment the answer by 1.
Finally, return the count of all the arithmetic subarray of size at least 3.

Time Complexity: O(N²)

Efficient approach: We will use a dynamic programming approach to maintain a count of all arithmetic sequences till any position.

Initialize a variable, res with 0. It will store the count of sequences.
Initialize a variable, count with 0. It will store the size of the sequence minus 2.
Increase the value of count if the current element forms an arithmetic sequence else make it zero.
If the current element L[i] is making an arithmetic sequence with L[i-1] and L[i-2], then the number of arithmetic sequences till the ith iteration is given by:

res = res + count

Finally, return the res variable.

Below is the implementation of the above approach:

C++

// C++ program to find all arithmetic
// sequences of size atleast 3
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find all arithmetic
// sequences of size atleast 3
int numberOfArithmeticSequences(int L[], int N)
{
 
    // If array size is less than 3
    if (N <= 2)
        return 0;
 
    // Finding arithmetic subarray length
    int count = 0;
 
    // To store all arithmetic subarray
    // of length at least 3
    int res = 0;
 
    for (int i = 2; i < N; ++i) {
 
        // Check if current element makes
        // arithmetic sequence with
        // previous two elements
        if (L[i] - L[i - 1] == L[i - 1] - L[i - 2]) {
            ++count;
        }
 
        // Begin with a new element for
        // new arithmetic sequences
        else {
            count = 0;
        }
 
        // Accumulate result in till i.
        res += count;
    }
 
    // Return final count
    return res;
}
 
// Driver code
int main()
{
 
    int L[] = { 1, 3, 5, 6, 7, 8 };
    int N = sizeof(L) / sizeof(L[0]);
 
    // Function to find arithmetic sequences
    cout << numberOfArithmeticSequences(L, N);
 
    return 0;
}

Java

// Java program to find all arithmetic
// sequences of size atleast 3
 
class GFG{
  
// Function to find all arithmetic
// sequences of size atleast 3
static int numberOfArithmeticSequences(int L[], int N)
{
  
    // If array size is less than 3
    if (N <= 2)
        return 0;
  
    // Finding arithmetic subarray length
    int count = 0;
  
    // To store all arithmetic subarray
    // of length at least 3
    int res = 0;
  
    for (int i = 2; i < N; ++i) {
 
        // Check if current element makes
        // arithmetic sequence with
        // previous two elements
        if (L[i] - L[i - 1] == L[i - 1] - L[i - 2]) {
            ++count;
        }
  
        // Begin with a new element for
        // new arithmetic sequences
        else {
            count = 0;
        }
  
        // Accumulate result in till i.
        res += count;
    }
  
    // Return final count
    return res;
}
  
// Driver code
public static void main(String[] args)
{
  
    int L[] = { 1, 3, 5, 6, 7, 8 };
    int N = L.length;
  
    // Function to find arithmetic sequences
    System.out.print(numberOfArithmeticSequences(L, N));
  
}
}
 
// This code contributed by sapnasingh4991

Python3

# Python3 program to find all arithmetic 
# sequences of size atleast 3 
 
# Function to find all arithmetic 
# sequences of size atleast 3 
def numberOfArithmeticSequences(L, N) :
 
    # If array size is less than 3 
    if (N <= 2) :
        return 0
 
    # Finding arithmetic subarray length 
    count = 0
 
    # To store all arithmetic subarray 
    # of length at least 3 
    res = 0
 
    for i in range(2,N): 
 
        # Check if current element makes 
        # arithmetic sequence with 
        # previous two elements 
        if ( (L[i] - L[i - 1]) == (L[i - 1] - L[i - 2])) :
            count += 1
 
        # Begin with a new element for 
        # new arithmetic sequences 
        else :
            count = 0
 
        # Accumulate result in till i. 
        res += count
 
 
    # Return final count 
    return res
 
# Driver code 
 
L = [ 1, 3, 5, 6, 7, 8 ]
N = len(L)
 
# Function to find arithmetic sequences 
print(numberOfArithmeticSequences(L, N))
 
# This code is contributed by Sanjit_Prasad

C#

// C# program to find all arithmetic
// sequences of size atleast 3
using System;
 
class GFG{
 
// Function to find all arithmetic
// sequences of size atleast 3
static int numberOfArithmeticSequences(int []L, 
                                       int N)
{
 
    // If array size is less than 3
    if (N <= 2)
        return 0;
 
    // Finding arithmetic subarray length
    int count = 0;
 
    // To store all arithmetic subarray
    // of length at least 3
    int res = 0;
 
    for(int i = 2; i < N; ++i)
    {
         
       // Check if current element makes
       // arithmetic sequence with
       // previous two elements
       if (L[i] - L[i - 1] ==
           L[i - 1] - L[i - 2])
       {
           ++count;
       }
        
       // Begin with a new element for
       // new arithmetic sequences
       else
       {
           count = 0;
       }
        
       // Accumulate result in till i.
       res += count;
    }
     
    // Return readonly count
    return res;
}
 
// Driver code
public static void Main(String[] args)
{
    int []L = { 1, 3, 5, 6, 7, 8 };
    int N = L.Length;
 
    // Function to find arithmetic sequences
    Console.Write(numberOfArithmeticSequences(L, N));
}
}
 
// This code is contributed by amal kumar choubey

Javascript

<script>
//Javascript program to find all arithmetic
// sequences of size atleast 3
 
 // Function to find all arithmetic
// sequences of size atleast 3
function numberOfArithmeticSequences( L, N)
{
 
    // If array size is less than 3
    if (N <= 2)
        return 0;
 
    // Finding arithmetic subarray length
    var count = 0;
 
    // To store all arithmetic subarray
    // of length at least 3
    var res = 0;
 
    for (var i = 2; i < N; ++i) {
 
        // Check if current element makes
        // arithmetic sequence with
        // previous two elements
        if (L[i] - L[i - 1] == L[i - 1] - L[i - 2]) {
            ++count;
        }
 
        // Begin with a new element for
        // new arithmetic sequences
        else {
            count = 0;
        }
 
        // Accumulate result in till i.
        res += count;
    }
 
    // Return final count
    return res;
}
 
var L = [ 1, 3, 5, 6, 7, 8 ];
    var N = L.length;
 
// Function to find arithmetic sequences
 document.write(numberOfArithmeticSequences(L, N));
   
  // This code contributed by SoumikMondal
</script>

Output:

Time Complexity: O(N)
Auxiliary Space: O(1)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!