Contar subarreglos con elementos consecutivos que difieren en 1

Dada una array arr[] de N enteros. La tarea es contar el número total de subarreglos de un arreglo dado de modo que la diferencia entre los elementos consecutivos en los subarreglos sea uno. Es decir, para cualquier índice  i     en los subarreglos, arr[i+1] – arr[i] = 1 .
Nota : No considere subarreglos con un solo elemento.
Ejemplos: 
 

Input : arr[] = {1, 2, 3}
Output : 3
The subarrays are {1, 2}. {2, 3} and {1, 2, 3}

Input : arr[] = {1, 2, 3, 5, 6, 7}
Output : 6

Enfoque ingenuo : un enfoque simple es ejecutar dos bucles anidados y verificar cada subarreglo y calcular el recuento de subarreglos con elementos consecutivos que difieren en 1.
Enfoque eficiente : un enfoque eficiente es observar que en un arreglo de longitud digamos K , el número total de subarreglos de tamaño mayor que 1 = (K)*(K-1)/2. 
Entonces, la idea es atravesar la array usando dos punteros para calcular subarreglos con elementos consecutivos en una ventana de longitud máxima y luego calcular todos los subarreglos en esa ventana usando la fórmula anterior.
A continuación se muestra el algoritmo paso a paso: 
 

  • Tome dos punteros para decir rápido y lento , para mantener una ventana de elementos consecutivos.
  • Comience a atravesar la array.
  • Si los elementos difieren en 1 incremento solo el puntero rápido.
  • De lo contrario, calcule la longitud de la ventana actual entre los índices rápido y lento .

A continuación se muestra la implementación del enfoque dado: 
 

C++

// C++ program to count Subarrays with
// Consecutive elements differing by 1
 
#include <iostream>
using namespace std;
 
// Function to count Subarrays with
// Consecutive elements differing by 1
int subarrayCount(int arr[], int n)
{
    // Variable to store count of subarrays
    // whose consecutive elements differ by 1
    int result = 0;
 
    // Take two pointers for maintaining a
    // window of consecutive elements
    int fast = 0, slow = 0;
 
    // Traverse the array
    for (int i = 1; i < n; i++) {
 
        // If elements differ by 1
        // increment only the fast pointer
        if (arr[i] - arr[i - 1] == 1) {
            fast++;
        }
        else {
 
            // Calculate length of subarray
            int len = fast - slow + 1;
 
            // Calculate total subarrays except
            // Subarrays with single element
            result += len * (len - 1) / 2;
 
            // Update fast and slow
            fast = i;
            slow = i;
        }
    }
 
    // For last iteration. That is if array is
    // traversed and fast > slow
    if (fast != slow) {
        int len = fast - slow + 1;
        result += len * (len - 1) / 2;
    }
 
    return result;
}
 
// Driver Code
int main()
{
 
    int arr[] = { 1, 2, 3, 5, 6, 7 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    cout << subarrayCount(arr, n);
 
    return 0;
}

Java

// Java program to count Subarrays with
// Consecutive elements differing by 1
class cfg
{
 
// Function to count Subarrays with
// Consecutive elements differing by 1
static int subarrayCount(int arr[], int n)
{
    // Variable to store count of subarrays
    // whose consecutive elements differ by 1
    int result = 0;
 
    // Take two pointers for maintaining a
    // window of consecutive elements
    int fast = 0, slow = 0;
 
    // Traverse the array
    for (int i = 1; i < n; i++) {
 
        // If elements differ by 1
        // increment only the fast pointer
        if (arr[i] - arr[i - 1] == 1) {
            fast++;
        }
        else {
 
            // Calculate length of subarray
            int len = fast - slow + 1;
 
            // Calculate total subarrays except
            // Subarrays with single element
            result += len * (len - 1) / 2;
 
            // Update fast and slow
            fast = i;
            slow = i;
        }
    }
 
    // For last iteration. That is if array is
    // traversed and fast > slow
    if (fast != slow) {
        int len = fast - slow + 1;
        result += len * (len - 1) / 2;
    }
 
    return result;
}
 
// Driver Code
public static void main(String[] args)
{
 
    int arr[] = { 1, 2, 3, 5, 6, 7 };
    int n = arr.length;
 
    System.out.println(subarrayCount(arr, n));
 
}
}
//This code is contributed by Mukul Singh

Python3

# Python3 program to count Subarrays with
# Consecutive elements differing by 1
 
# Function to count Subarrays with
# Consecutive elements differing by 1
def subarrayCount(arr, n) :
     
    # Variable to store count of subarrays
    # whose consecutive elements differ by 1
    result = 0
 
    # Take two pointers for maintaining a
    # window of consecutive elements
    fast, slow = 0, 0
 
    # Traverse the array
    for i in range(1, n) :
 
        # If elements differ by 1
        # increment only the fast pointer
        if (arr[i] - arr[i - 1] == 1) :
            fast += 1
         
        else :
 
            # Calculate length of subarray
            length = fast - slow + 1
 
            # Calculate total subarrays except
            # Subarrays with single element
            result += length * (length - 1) // 2;
 
            # Update fast and slow
            fast = i
            slow = i
 
    # For last iteration. That is if array is
    # traversed and fast > slow
    if (fast != slow) :
        length = fast - slow + 1
        result += length * (length - 1) // 2;
     
    return result
 
# Driver Code
if __name__ == "__main__" :
 
    arr = [ 1, 2, 3, 5, 6, 7 ]
    n = len(arr)
 
    print(subarrayCount(arr, n))
 
# This code is contributed by Ryuga

C#

// C# program to count Subarrays with
// Consecutive elements differing by 1
using System;
class cfg
{
 
// Function to count Subarrays with
// Consecutive elements differing by 1
static int subarrayCount(int []arr, int n)
{
    // Variable to store count of subarrays
    // whose consecutive elements differ by 1
    int result = 0;
 
    // Take two pointers for maintaining a
    // window of consecutive elements
    int fast = 0, slow = 0;
 
    // Traverse the array
    for (int i = 1; i < n; i++) {
 
        // If elements differ by 1
        // increment only the fast pointer
        if (arr[i] - arr[i - 1] == 1) {
            fast++;
        }
        else {
 
            // Calculate length of subarray
            int len = fast - slow + 1;
 
            // Calculate total subarrays except
            // Subarrays with single element
            result += len * (len - 1) / 2;
 
            // Update fast and slow
            fast = i;
            slow = i;
        }
    }
 
    // For last iteration. That is if array is
    // traversed and fast > slow
    if (fast != slow) {
        int len = fast - slow + 1;
        result += len * (len - 1) / 2;
    }
 
    return result;
}
 
// Driver Code
public static void Main()
{
 
    int []arr = { 1, 2, 3, 5, 6, 7 };
    int n = arr.Length;
 
    Console.WriteLine(subarrayCount(arr, n));
 
}
}
//This code is contributed by inder_verma..

PHP

<?php
// PHP program to count Subarrays with
// Consecutive elements differing by 1
 
// Function to count Subarrays with
// Consecutive elements differing by 1
function subarrayCount($arr, $n)
{
    // Variable to store count of subarrays
    // whose consecutive elements differ by 1
    $result = 0;
 
    // Take two pointers for maintaining a
    // window of consecutive elements
    $fast = 0; $slow = 0;
 
    // Traverse the array
    for ($i = 1; $i < $n; $i++)
    {
 
        // If elements differ by 1
        // increment only the fast pointer
        if ($arr[$i] - $arr[$i - 1] == 1)
        {
            $fast++;
        }
        else
        {
 
            // Calculate length of subarray
            $len = $fast - $slow + 1;
 
            // Calculate total subarrays except
            // Subarrays with single element
            $result += $len * ($len - 1) / 2;
 
            // Update fast and slow
            $fast = $i;
            $slow = $i;
        }
    }
 
    // For last iteration. That is if array
    // is traversed and fast > slow
    if ($fast != $slow)
    {
        $len = $fast - $slow + 1;
        $result += $len * ($len - 1) / 2;
    }
 
    return $result;
}
 
// Driver Code
$arr = array(1, 2, 3, 5, 6, 7);
$n = sizeof($arr);
 
echo subarrayCount($arr, $n);
 
// This code is contributed
// by Akanksha Rai
?>

Javascript

<script>
 
// Javascript program to count Subarrays with
// Consecutive elements differing by 1
 
 
    // Function to count Subarrays with
    // Consecutive elements differing by 1
    function subarrayCount(arr , n) {
        // Variable to store count of subarrays
        // whose consecutive elements differ by 1
        var result = 0;
 
        // Take two pointers for maintaining a
        // window of consecutive elements
        var fast = 0, slow = 0;
 
        // Traverse the array
        for (i = 1; i < n; i++) {
 
            // If elements differ by 1
            // increment only the fast pointer
            if (arr[i] - arr[i - 1] == 1) {
                fast++;
            } else {
 
                // Calculate length of subarray
                var len = fast - slow + 1;
 
                // Calculate total subarrays except
                // Subarrays with single element
                result += len * (len - 1) / 2;
 
                // Update fast and slow
                fast = i;
                slow = i;
            }
        }
 
        // For last iteration. That is if array is
        // traversed and fast > slow
        if (fast != slow) {
            var len = fast - slow + 1;
            result += len * (len - 1) / 2;
        }
 
        return result;
    }
 
    // Driver Code
     
 
        var arr = [ 1, 2, 3, 5, 6, 7 ];
        var n = arr.length;
 
        document.write(subarrayCount(arr, n));
 
 
// This code contributed by aashish1995
 
</script>
Producción: 

6

 

Complejidad de tiempo : O(N), ya que estamos usando un bucle para recorrer N veces, por lo que la complejidad del programa será O(N).
Espacio auxiliar : O(1), ya que no estamos utilizando ningún espacio adicional.
 

Publicación traducida automáticamente

Artículo escrito por Striver y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *