Saturday, 23 Oct 2021

# Queries to check if array elements from indices [L, R] forms an Arithmetic Progression or not

Queries to check if array elements from indices [L, R] forms an Arithmetic Progression or notGiven an array arr[] consisting of N integers and an array Q[] consisting of M queries of the form {L, R}, the task for each query is to check if array elements over the range [L, R] forms an Arithmetic Progression or not. If found to be true, print “Yes”. Otherwise, print “No”.Examples:Input: arr[] = {1, 3, 5, 7, 6, 5, 4, 1}, Q[][] = {{0, 3}, {3, 4}, {2, 4}}Output:YesYesNoExplanation: Query 1: The elements of the array over the range [0, 3] are {1, 3, 5, 7} which forms an arithmetic series with a common difference of 2. Hence, print “Yes”.Query 2: The elements of the array over the range [3, 4 are {7, 6} which forms an arithmetic series with a common difference of -1. Hence, print “Yes”.Query 3: The elements of the array over the range [2, 4 are {5, 7, 6}, which does not form an arithmetic series. Hence, print “Yes”.Input: arr[] = {1, 2}, Q[][] = {{0, 0}, {0, 1}, {0, 1}}Output:YesYesYesNaive Approach: The simplest approach to solve the problem is to traverse the given array over the range [L, R] for each query and check if the common difference between all the adjacent elements is the same or not. If the difference is the same, then print “Yes”. Otherwise, print “No”.Time Complexity: O(N*M)Auxiliary Space: O(1)Efficient Approach: The above approach can be optimized based on the following observations:The idea is to precompute the longest length of the subarray forming an AP starting from any index i for every ith element of the array in an auxiliary array say dp[] using the Two Pointer Algorithm.For a given range [L, R], if the value of dp[L] is greater than or equal to (R – L), then the range will always form an AP as (R – L) is the current range of elements and dp[L] stores the length of the longest subarray forming AP from index L, then the subarray length must be smaller than dp[L].Follow the steps below to solve the problem:Initialize an array say dp[] to store the length of the longest subarray starting from each index for each element at that index. Iterate over the range [0, N] using the variable i and perform the following steps:Initialize a variable say j as (i + 1) to store the last index array forming Arithmetic Progression from index i.Increment the value of j until (j + 1 < N) and (arr[j] – arr[j – 1]) is same as (arr[i + 1] – arr[i]).Iterate over the range [i, j – 1] using the variable, say K, and update the value of dp[K] as (j – K).Update the value of i as j.Traverse the given array of queries Q[] and for each query {L, R} if the value of dp[L] is greater than or equal to (R – L), then print “Yes”. Otherwise, print “No”.Below is the implementation of the above approach:C++  #include using namespace std;  void findAPSequence(int arr[], int N,                    int Q[], int M){                int dp[N + 5] = { 0 };          for (int i = 0; i + 1 < N;) {                          int j = i + 1;                          while (j + 1 < N               && arr[j + 1] - arr[j]                      == arr[i + 1] - arr[i])                          j++;                          for (int k = i; k < j; k++) {                                      dp[k] = j - k;        }                  i = j;    }          for (int i = 0; i < M; i++) {                  if (dp[Q[i]]            >= Q[i] – Q[i]) {            cout