Dada una array arr[] de tamaño N , la tarea es encontrar el recuento de subarreglos de al menos una longitud de 2, de modo que la diferencia entre los elementos consecutivos de esos subarreglos permanezca igual, es decir, los elementos del subarreglo forman un AP.
Ejemplos:
Entrada: arr[] = {8, 7, 4, 1, 0}
Salida: 5
Explicación:
Todos los subarreglos de tamaño mayor que 1 que forman un AP son [8, 7], [7, 4], [4, 1 ], [1, 0], [7, 4, 1]Entrada: arr[] = {4, 2}
Salida: 1
Enfoque: la idea es generar todos los subarreglos posibles a partir del arreglo dado y, para cada subarreglo, verificar si la diferencia entre los elementos adyacentes es la misma o no para los subarreglos generados. A continuación se muestran los pasos:
- Iterar sobre cada subarreglo de longitud de al menos 2 usando dos bucles.
- Sea i el índice inicial del subarreglo y j el índice final del subarreglo.
- Si la diferencia entre cada par de elementos adyacentes de la array desde el índice i al j es la misma, incremente el recuento total.
- De lo contrario, repita el proceso anterior con el siguiente subarreglo.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of
// the above approach
#include <iostream>
using namespace std;
// Function to find the
// total count of subarrays
int calcSubarray(int A[], int N)
{
int count = 0;
// Iterate over each subarray
for (int i = 0; i < N; i++) {
for (int j = i + 1; j < N; j++) {
bool flag = true;
// Difference between first
// two terms of subarray
int comm_diff = A[i + 1] - A[i];
// Iterate over the subarray
// from i to j
for (int k = i; k < j; k++) {
// Check if the difference
// of all adjacent elements
// is same
if (A[k + 1] - A[k] == comm_diff) {
continue;
}
else {
flag = false;
break;
}
}
if (flag) {
count++;
}
}
}
return count;
}
// Driver Code
int main()
{
// Given array
int A[5] = { 8, 7, 4, 1, 0 };
int N = sizeof(A) / sizeof(int);
// Function Call
cout << calcSubarray(A, N);
}
Java
// Java implementation of
// the above approach
import java.util.*;
class GFG{
// Function to find the
// total count of subarrays
static int calcSubarray(int A[],
int N)
{
int count = 0;
// Iterate over each subarray
for (int i = 0; i < N; i++)
{
for (int j = i + 1; j < N; j++)
{
boolean flag = true;
// Difference between first
// two terms of subarray
int comm_diff = A[i + 1] - A[i];
// Iterate over the subarray
// from i to j
for (int k = i; k < j; k++)
{
// Check if the difference
// of all adjacent elements
// is same
if (A[k + 1] - A[k] == comm_diff)
{
continue;
}
else
{
flag = false;
break;
}
}
if (flag)
{
count++;
}
}
}
return count;
}
// Driver Code
public static void main(String[] args)
{
// Given array
int []A = {8, 7, 4, 1, 0};
int N = A.length;
// Function Call
System.out.print(calcSubarray(A, N));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 implementation of # the above approach # Function to find the # total count of subarrays def calcSubarray(A, N): count = 0 # Iterate over each subarray for i in range(N): for j in range(i + 1, N): flag = True # Difference between first # two terms of subarray comm_diff = A[i + 1] - A[i] # Iterate over the subarray # from i to j for k in range(i, j): # Check if the difference # of all adjacent elements # is same if (A[k + 1] - A[k] == comm_diff): continue else: flag = False break if (flag): count += 1 return count # Driver Code if __name__ == '__main__': # Given array A = [ 8, 7, 4, 1, 0 ] N = len(A) # Function call print(calcSubarray(A, N)) # This code is contributed by mohit kumar 29
C#
// C# implementation of
// the above approach
using System;
class GFG{
// Function to find the
// total count of subarrays
static int calcSubarray(int []A,
int N)
{
int count = 0;
// Iterate over each subarray
for (int i = 0; i < N; i++)
{
for (int j = i + 1; j < N; j++)
{
bool flag = true;
// Difference between first
// two terms of subarray
int comm_diff = A[i + 1] - A[i];
// Iterate over the subarray
// from i to j
for (int k = i; k < j; k++)
{
// Check if the difference
// of all adjacent elements
// is same
if (A[k + 1] - A[k] == comm_diff)
{
continue;
}
else
{
flag = false;
break;
}
}
if (flag)
{
count++;
}
}
}
return count;
}
// Driver Code
public static void Main(String[] args)
{
// Given array
int []A = {8, 7, 4, 1, 0};
int N = A.Length;
// Function Call
Console.Write(calcSubarray(A, N));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript implementation of
// the above approach
// Function to find the
// total count of subarrays
function calcSubarray(A, N)
{
let count = 0;
// Iterate over each subarray
for (let i = 0; i < N; i++) {
for (let j = i + 1; j < N; j++) {
let flag = true;
// Difference between first
// two terms of subarray
let comm_diff = A[i + 1] - A[i];
// Iterate over the subarray
// from i to j
for (let k = i; k < j; k++) {
// Check if the difference
// of all adjacent elements
// is same
if (A[k + 1] - A[k] == comm_diff) {
continue;
}
else {
flag = false;
break;
}
}
if (flag) {
count++;
}
}
}
return count;
}
// Driver Code
// Given array
let A = [ 8, 7, 4, 1, 0 ];
let N = A.length;
// Function Call
document.write(calcSubarray(A, N));
// This code is contributed by Mayank Tyagi
</script>
5
Complejidad de Tiempo: O(N 3 )
Espacio Auxiliar: O(1)
Método 2: (Iterar sobre la array solo una vez)
Acercarse:
La idea es iterar en el arreglo solo una vez mientras se compara la diferencia entre elementos adyacentes y se cuenta el número de elementos en cada subarreglo más grande para esa diferencia que se almacena en la variable t .
Por ejemplo, considere la array: {1, 2, 3, 7}. Aquí el subarreglo más grande con diferencia = 1 es {1, 2, 3}. Así que aquí t = 3 y los posibles subarreglos de longitud de al menos 2 son {1, 2, 3}, {1, 2} y {2, 3}.
De manera similar, el subarreglo más grande con diferencia = 4 es {3, 7}. Así que aquí t = 2 y los posibles subarreglos de longitud de al menos 2 son {3, 7}.
Por lo tanto, los subarreglos aritméticos totales con una longitud de al menos 2 son 3 + 1 = 4.
Para derivar posibles subarreglos para una diferencia particular, usaremos la fórmula matemática de la siguiente manera:
(t * (t + 1) ) / 2 – t.
Entendamos cómo obtuvimos esta fórmula.
Supongamos que este es un subarreglo {1, 2, 3, 4, 5} de algún otro arreglo más grande. El total de subarreglos con diferencia aritmética y longitud de al menos 2 utilizando este subarreglo será el siguiente,
{1, 2, 3, 4, 5} = 1
{1, 2, 3, 4}, {2, 3, 4, 5} = 2
{1, 2, 3}, {2, 3, 4}, {3, 4, 5} = 3
{1, 2}, {2, 3}, {3, 4}, {4, 5} = 4
Y número total de subarreglos = 1 + 2 + 3 + 4
Esto no es más que la suma de los primeros (t – 1) números consecutivos = (t * (t + 1)) / 2 – t.
De manera similar, si tuviéramos que encontrar subarreglos aritméticos con una longitud de al menos 3 , entonces consideraríamos lo siguiente,
{1, 2, 3, 4, 5} = 1
{1, 2, 3, 4}, {2, 3, 4, 5} = 2
{1, 2, 3}, {2, 3, 4}, {3, 4, 5} = 3
Y número total de subarreglos en este caso = 1 + 2 + 3 para t = 5
La fórmula matemática excluirá 4 ie (t – 1) y 5 ie t de su suma, por lo que la fórmula será
(t * (t + 1)) / 2 – (t – 1) – (t) = (t * (t + 1)) / 2 – (2 * t) + 1
Para contar el número máximo de elementos en un subarreglo con una diferencia particular, usamos la variable num .
La variable d rastrea la diferencia. d se inicializa a la diferencia entre el segundo y el primer elemento y num será 1 ya que para subarreglos con 2 elementos, el total de subarreglos posibles para esa diferencia será 1.
Luego i se incrementa a 1 y comenzamos a iterar en la array.
- Si la diferencia entre elementos adyacentes coincide con la diferencia en la variable d , simplemente incrementamos el num .
- Si la diferencia entre elementos adyacentes no coincide con la variable d , obtuvimos el subarreglo con el número máximo de elementos para esa diferencia.
- El valor de t ie número máximo de elementos para esa diferencia será ( num + 1). Así que usamos la fórmula matemática para sumar el número de subarreglos para la longitud t .
- Restablecemos el num a 1 para un nuevo subarreglo y d a la nueva diferencia para la próxima comparación y continuamos con el Paso 1.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the
// total count of subarrays
int calcSubarray(int A[], int N)
{
// If size of array is smaller than 2,
// then count will be zero
if (N < 2) {
return 0;
}
int i = 0;
int num, d, count = 0, t;
// Difference between first two adjacent array elements
d = A[i + 1] - A[i];
// num stores the total number of elements in a subarray
// for a particular difference
num = 1;
// After calculating difference, move to next element
// and iterate over the array
i = 1;
while (i < N - 1) {
// If Difference between adjacent elements is same
// as d, increment num
if (A[i + 1] - A[i] == d) {
num++;
}
else {
// Update the count if number of elements
// in subarray is greater than 1
if (num >= 1) {
t = num + 1;
count = count + (t * (t + 1)) / 2 - t;
}
// Reset num
num = 1;
// Update with new difference
d = A[i + 1] - A[i];
}
i++;
}
if (num >= 1) {
t = num + 1;
count = count + (t * (t + 1)) / 2 - t;
}
return count;
}
// Driver Code
int main()
{
// Given Array
int A[5] = { 8, 7, 4, 1, 0 };
int N = sizeof(A) / sizeof(int);
// Function Call
cout << calcSubarray(A, N);
return 0;
// This code is contributed by Snigdha Patil
}
Python3
# Python implementation of # the above approach # Function to find the # total count of subarrays def calcSubarray(A,N): # If size of array is smaller than 2, # then count will be zero if (N < 2): return 0 i = 0 num = 0 count = 0 t = 0 # Difference between first two adjacent array elements d = A[i + 1] - A[i] # num stores the total number of elements in a subarray # for a particular difference num = 1 # After calculating difference, move to next element # and iterate over the array i = 1 while (i < N - 1): # If Difference between adjacent elements is same # as d, increment num if (A[i + 1] - A[i] == d): num += 1 else: # Update the count if number of elements # in subarray is greater than 1 if (num >= 1): t = num + 1 count = count + (t * (t + 1)) // 2 - t # Reset num num = 1 # Update with new difference d = A[i + 1] - A[i] i += 1 if (num >= 1): t = num + 1 count = count + (t * (t + 1)) // 2 - t return count # Driver Code # Given Array A = [ 8, 7, 4, 1, 0 ] N = len(A) # Function Call print(calcSubarray(A, N)) # This code is contributed by Shinjanpatra
Javascript
<script>
// JavaScript implementation of
// the above approach
// Function to find the
// total count of subarrays
function calcSubarray(A, N)
{
// If size of array is smaller than 2,
// then count will be zero
if (N < 2) {
return 0;
}
let i = 0;
let num, d, count = 0, t;
// Difference between first two adjacent array elements
d = A[i + 1] - A[i];
// num stores the total number of elements in a subarray
// for a particular difference
num = 1;
// After calculating difference, move to next element
// and iterate over the array
i = 1;
while (i < N - 1) {
// If Difference between adjacent elements is same
// as d, increment num
if (A[i + 1] - A[i] == d) {
num++;
}
else {
// Update the count if number of elements
// in subarray is greater than 1
if (num >= 1) {
t = num + 1;
count = count + Math.floor((t * (t + 1)) / 2) - t;
}
// Reset num
num = 1;
// Update with new difference
d = A[i + 1] - A[i];
}
i++;
}
if (num >= 1) {
t = num + 1;
count = count + Math.floor((t * (t + 1)) / 2) - t;
}
return count;
}
// Driver Code
// Given Array
let A = [ 8, 7, 4, 1, 0 ];
let N = A.length;
// Function Call
document.write(calcSubarray(A, N));
// This code is contributed by Shinjanpatra
</script>
5
Complejidad de tiempo: O(N)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por kritirikhi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA