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(N2)
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 3int 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 codeint 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 3class GFG{ // Function to find all arithmetic// sequences of size atleast 3static 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 codepublic 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 3using System;class GFG{// Function to find all arithmetic// sequences of size atleast 3static 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 codepublic 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 3function 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:
4
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
