Dada una array arr[] que consta de N enteros y una array Q[][2] que consta de M consultas de la forma {L, R} , la tarea de cada consulta es verificar si los elementos de la array están sobre el rango [L, R ] forma una progresión aritmética o no. Si es cierto , escriba “Sí” . De lo contrario, escriba “No”.
Ejemplos:
Entrada: arr[] = {1, 3, 5, 7, 6, 5, 4, 1}, Q[][] = {{0, 3}, {3, 4}, {2, 4}}
Salida :
Sí
Sí
No
Explicación:
Consulta 1: Los elementos de la array sobre el rango [0, 3] son {1, 3, 5, 7} que forman una serie aritmética con una diferencia común de 2. Por lo tanto, imprime «Sí» .
Consulta 2: Los elementos de la array sobre el rango [3, 4 son {7, 6} que forman una serie aritmética con una diferencia común de -1. Por lo tanto, imprima «Sí».
Consulta 3: Los elementos de la array sobre el rango [2, 4 son {5, 7, 6}, que no forman una serie aritmética. Por lo tanto, imprima «Sí».Entrada: arr[] = {1, 2}, Q[][] = {{0, 0}, {0, 1}, {0, 1}}
Salida:
Sí
Sí
Sí
Enfoque ingenuo: el enfoque más simple para resolver el problema es atravesar la array dada en el rango [L, R] para cada consulta y verificar si la diferencia común entre todos los elementos adyacentes es la misma o no. Si la diferencia es la misma, imprima «Sí» . De lo contrario, escriba “No” .
Complejidad temporal: O(N*M)
Espacio auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar en función de las siguientes observaciones:
- La idea es precalcular la longitud más larga del subarreglo que forma un AP a partir de cualquier índice i para cada i -ésimo elemento del arreglo en un arreglo auxiliar, digamos dp[] usando el algoritmo de dos punteros .
- Para un rango dado [L, R] , si el valor de dp[L] es mayor o igual a (R – L) , entonces el rango siempre formará un AP ya que (R – L) es el rango actual de elementos y dp[L] almacena la longitud del subarreglo más largo que forma AP a partir del índice L , entonces la longitud del subarreglo debe ser menor que dp[L] .
Siga los pasos a continuación para resolver el problema:
- Inicialice un arreglo, digamos dp[] para almacenar la longitud del subarreglo más largo a partir de cada índice para cada elemento en ese índice.
- Iterar sobre el rango [0, N] usando la variable i y realizar los siguientes pasos:
- Inicialice una variable, digamos j como (i + 1) para almacenar la última array de índice que forma la Progresión aritmética desde el índice i .
- Incremente el valor de j hasta que (j + 1 < N) y (arr[j] – arr[j – 1]) sea igual a (arr[i + 1] – arr[i]).
- Itere sobre el rango [i, j – 1] usando la variable, digamos K , y actualice el valor de dp[K] como (j – K) .
- Actualice el valor de i como j .
- Recorra la array dada de consultas Q[] y para cada consulta {L, R} si el valor de dp[L] es mayor o igual que (R – L) , luego imprima «Sí» . De lo contrario, escriba “No”.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if the given range
// of queries form an AP or not in the
// given array arr[]
void findAPSequence(int arr[], int N,
int Q[][2], int M)
{
// Stores length of the longest
// subarray forming AP for every
// array element
int dp[N + 5] = { 0 };
// Iterate over the range [0, N]
for (int i = 0; i + 1 < N;) {
// Stores the index of the last
// element of forming AP
int j = i + 1;
// Iterate until the element at
// index (j, j + 1) forms AP
while (j + 1 < N
&& arr[j + 1] - arr[j]
== arr[i + 1] - arr[i])
// Increment j by 1
j++;
// Traverse the current subarray
// over the range [i, j - 1]
for (int k = i; k < j; k++) {
// Update the length of the
// longest subarray at index k
dp[k] = j - k;
}
// Update the value of i
i = j;
}
// Traverse the given queries
for (int i = 0; i < M; i++) {
// Print the result
if (dp[Q[i][0]]
>= Q[i][1] - Q[i][0]) {
cout << "Yes" << endl;
}
// Otherwise
else {
cout << "No" << endl;
}
}
}
// Driver Code
int main()
{
int arr[] = { 1, 3, 5, 7, 6, 5, 4, 1 };
int Q[][2] = { { 0, 3 }, { 3, 4 }, { 2, 4 } };
int N = sizeof(arr) / sizeof(arr[0]);
int M = sizeof(Q) / sizeof(Q[0]);
findAPSequence(arr, N, Q, M);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG{
// Function to check if the given range
// of queries form an AP or not in the
// given array arr[]
static void findAPSequence(int arr[], int N,
int Q[][], int M)
{
// Stores length of the longest
// subarray forming AP for every
// array element
int dp[] = new int[N + 5];
// Iterate over the range [0, N]
for(int i = 0; i + 1 < N;)
{
// Stores the index of the last
// element of forming AP
int j = i + 1;
// Iterate until the element at
// index (j, j + 1) forms AP
while (j + 1 < N && arr[j + 1] - arr[j] ==
arr[i + 1] - arr[i])
// Increment j by 1
j++;
// Traverse the current subarray
// over the range [i, j - 1]
for(int k = i; k < j; k++)
{
// Update the length of the
// longest subarray at index k
dp[k] = j - k;
}
// Update the value of i
i = j;
}
// Traverse the given queries
for(int i = 0; i < M; i++)
{
// Print the result
if (dp[Q[i][0]] >= Q[i][1] - Q[i][0])
{
System.out.println("Yes");
}
// Otherwise
else
{
System.out.println("No");
}
}
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 1, 3, 5, 7, 6, 5, 4, 1 };
int Q[][] = { { 0, 3 }, { 3, 4 }, { 2, 4 } };
int N = arr.length;
int M = Q.length;
findAPSequence(arr, N, Q, M);
}
}
// This code is contributed by Kingash
Python3
# Python3 program for the above approach
# Function to check if the given range
# of queries form an AP or not in the
# given array arr[]
def findAPSequence(arr, N, Q, M):
# Stores length of the longest
# subarray forming AP for every
# array element
dp = [0] * (N + 5)
# Iterate over the range [0, N]
i = 0
while i + 1 < N:
# Stores the index of the last
# element of forming AP
j = i + 1
# Iterate until the element at
# index (j, j + 1) forms AP
while (j + 1 < N and
arr[j + 1] - arr[j] ==
arr[i + 1] - arr[i]):
# Increment j by 1
j += 1
# Traverse the current subarray
# over the range [i, j - 1]
for k in range(i, j):
# Update the length of the
# longest subarray at index k
dp[k] = j - k
# Update the value of i
i = j
# Traverse the given queries
for i in range(M):
# Print the result
if (dp[Q[i][0]] >= Q[i][1] - Q[i][0]):
print("Yes")
# Otherwise
else:
print("No")
# Driver Code
if __name__ == "__main__":
arr = [ 1, 3, 5, 7, 6, 5, 4, 1 ]
Q = [ [ 0, 3 ], [ 3, 4 ], [ 2, 4 ] ]
N = len(arr)
M = len(Q)
findAPSequence(arr, N, Q, M)
# This code is contributed by ukasp
C#
// C# code for above approach
using System;
public class GFG
{
// Function to check if the given range
// of queries form an AP or not in the
// given array arr[]
static void findAPSequence(int[] arr, int N,
int[, ] Q, int M)
{
// Stores length of the longest
// subarray forming AP for every
// array element
int[] dp = new int[N + 5];
// Iterate over the range [0, N]
for(int i = 0; i + 1 < N;)
{
// Stores the index of the last
// element of forming AP
int j = i + 1;
// Iterate until the element at
// index (j, j + 1) forms AP
while (j + 1 < N && arr[j + 1] - arr[j] ==
arr[i + 1] - arr[i])
// Increment j by 1
j++;
// Traverse the current subarray
// over the range [i, j - 1]
for(int k = i; k < j; k++)
{
// Update the length of the
// longest subarray at index k
dp[k] = j - k;
}
// Update the value of i
i = j;
}
// Traverse the given queries
for(int i = 0; i < M; i++)
{
// Print the result
if (dp[Q[i, 0]] >= Q[i, 1] - Q[i, 0])
{
Console.WriteLine("Yes");
}
// Otherwise
else
{
Console.WriteLine("No");
}
}
}
static public void Main (){
int[] arr = { 1, 3, 5, 7, 6, 5, 4, 1 };
int[, ] Q = { { 0, 3 }, { 3, 4 }, { 2, 4 } };
int N = arr.Length;
int M = Q.GetLength(0);
findAPSequence(arr, N, Q, M);
}
}
// This code is contributed by offbeat
Javascript
<script>
// javascript program for the above approach
// Function to check if the given range
// of queries form an AP or not in the
// given array arr
function findAPSequence(arr , N , Q , M) {
// Stores length of the longest
// subarray forming AP for every
// array element
var dp = Array(N + 5).fill(0);
// Iterate over the range [0, N]
for (i = 0; i + 1 < N;) {
// Stores the index of the last
// element of forming AP
var j = i + 1;
// Iterate until the element at
// index (j, j + 1) forms AP
while (j + 1 < N && arr[j + 1] - arr[j] == arr[i + 1] - arr[i])
// Increment j by 1
j++;
// Traverse the current subarray
// over the range [i, j - 1]
for (k = i; k < j; k++) {
// Update the length of the
// longest subarray at index k
dp[k] = j - k;
}
// Update the value of i
i = j;
}
// Traverse the given queries
for (i = 0; i < M; i++) {
// Print the result
if (dp[Q[i][0]] >= Q[i][1] - Q[i][0]) {
document.write("Yes <br/>");
}
// Otherwise
else {
document.write("No <br/>");
}
}
}
// Driver Code
var arr = [ 1, 3, 5, 7, 6, 5, 4, 1 ];
var Q = [ [ 0, 3 ], [ 3, 4 ], [ 2, 4 ] ];
var N = arr.length;
var M = Q.length;
findAPSequence(arr, N, Q, M);
// This code contributed by umadevi9616
</script>
Producción:
Yes Yes No
Complejidad temporal: O(N + M)
Espacio auxiliar: O(N)