Cuente los subarreglos de modo que el resto después de dividir la suma de los elementos por K proporcione la cuenta de los elementos

Dada una array arr[] de tamaño N y un elemento K . La tarea es encontrar el número de subarreglos del arreglo dado tal que el resto al dividir la suma de sus elementos por K sea igual al número de elementos en el subarreglo.

Ejemplos: 

Entrada: arr[] = {1, 4, 2, 3, 5}, K = 4 
Salida: 4 
{1}, {1, 4, 2}, {4, 2} y {5} 
son los únicos subarreglos válidos .
Entrada: arr[] = {4, 2, 4, 2, 4, 2, 4, 2}, K = 4 
Salida: 7 

Planteamiento: Definamos una sucesión S _n tal que S _i = A ₁ + A ₂ + ··· + A _i y S ₀ = 0 . Entonces, la condición de que una subsecuencia contigua A _i+1 , …, A _j sea válida se puede representar como (S _j – S _i ​​) % K = j – i . 
Esta ecuación se puede transformar en las siguientes condiciones equivalentes: 
(S _j – j) % K = (S _i – i) % K y j – i < K . 
Por lo tanto, para cadaj(1 ≤ j ≤ N) , cuente el número de j – K < yo < j tal que (S _j – j) % K = (S _yo – i) % K . Para j, el segmento que se necesita buscar es (j – K, j) , y para j + 1 , es (j – K + 1, j + 1) , y estos difieren solo en un elemento en el extremo izquierdo y derecho, entonces, para buscar (j + 1) ^después de buscar ^el elemento j , solo descarte el elemento más a la izquierda y agregue el elemento más a la derecha. Las operaciones de descartar o agregar se pueden realizar rápidamente administrando el número de S _i – i‘s mediante el uso de arrays asociativas (como map en C++ o dict en Python).

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

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the number of subarrays
// of the given array such that the remainder
// when dividing the sum of its elements
// by K is equal to the number of its elements
int sub_arrays(int a[], int n, int k)
{
 
    // To store prefix sum
    int sum[n + 2] = { 0 };
 
    for (int i = 0; i < n; i++) {
 
        // We are dealing with zero
        // indexed array
        a[i]--;
 
        // Taking modulus value
        a[i] %= k;
 
        // Prefix sum
        sum[i + 1] += sum[i] + a[i];
        sum[i + 1] %= k;
    }
 
    // To store the required answer, the left
    // index and the right index
    int ans = 0, l = 0, r = 0;
 
    // To store si - i value
    map<int, int> mp;
 
    for (int i = 0; i < n + 1; i++) {
 
        // Include sum
        ans += mp[sum[i]];
        mp[sum[i]]++;
 
        // Increment the right index
        r++;
 
        // If subarray has at least
        // k elements
        if (r - l >= k) {
            mp[sum[l]]--;
            l++;
        }
    }
 
    // Return the required answer
    return ans;
}
 
// Driver code
int main()
{
    int a[] = { 1, 4, 2, 3, 5 };
    int n = sizeof(a) / sizeof(a[0]);
 
    int k = 4;
 
    // Function call
    cout << sub_arrays(a, n, k);
 
    return 0;
}

// Java implementation of the approach
import java.util.*;
 
class gfg
{
     
    // Function to return the number of subarrays
    // of the given array such that the remainder
    // when dividing the sum of its elements
    // by K is equal to the number of its elements
    static int sub_arrays(int []a, int n, int k)
    {
     
        // To store prefix sum
        int sum[] = new int[n + 2] ;
         
        for (int i = 0; i < n+2; i++)
        {
            sum[i] = 0;
        }
         
        for (int i = 0; i < n; i++)
        {
     
            // We are dealing with zero
            // indexed array
            a[i]--;
     
            // Taking modulus value
            a[i] %= k;
     
            // Prefix sum
            sum[i + 1] += sum[i] + a[i];
            sum[i + 1] %= k;
        }
     
        // To store the required answer, the left
        // index and the right index
        int ans = 0, l = 0, r = 0;
     
        // To store si - i value
        HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>();
     
        for (int i = 0; i < n + 1; i++)
        {
            mp.put(sum[i], 0);
        }
        int temp;
         
        for (int i = 0; i < n + 1; i++)
        {
     
            // Include sum
            ans += (int)mp.get(sum[i]);
            temp =(int)mp.get(sum[i]) + 1;
            mp.put(sum[i], temp);
     
            // Increment the right index
            r++;
     
            // If subarray has at least
            // k elements
            if (r - l >= k)
            {
                //mp[sum[l]]--;
                temp = (int)mp.get(sum[l]) - 1;
                mp.put(sum[l], temp);
                l++;
            }
        }
     
        // Return the required answer
        return ans;
    }
     
    // Driver code
    public static void main(String args[])
    {
        int []a = { 1, 4, 2, 3, 5 };
         
        int n = a.length;
     
        int k = 4;
     
        // Function call
        System.out.print(sub_arrays(a, n, k));
     
    }
}
 
// This code is contributed by AnkitRai01

# Python3 implementation of the approach
 
# Function to return the number of
# subarrays of the given array
# such that the remainder when dividing
# the sum of its elements by K is
# equal to the number of its elements
def sub_arrays(a, n, k):
 
    # To store prefix sum
    sum = [0 for i in range(n + 2)]
 
    for i in range(n):
 
        # We are dealing with zero
        # indexed array
        a[i] -= 1
 
        # Taking modulus value
        a[i] %= k
 
        # Prefix sum
        sum[i + 1] += sum[i] + a[i]
        sum[i + 1] %= k
 
    # To store the required answer,
    # the left index and the right index
    ans = 0
    l = 0
    r = 0
 
    # To store si - i value
    mp = dict()
 
    for i in range(n + 1):
 
        # Include sum
        if sum[i] in mp:
            ans += mp[sum[i]]
        mp[sum[i]] = mp.get(sum[i], 0) + 1
 
        # Increment the right index
        r += 1
 
        # If subarray has at least
        # k elements
        if (r - l >= k):
            mp[sum[l]] -= 1
            l += 1
 
    # Return the required answer
    return ans
 
# Driver code
a = [1, 4, 2, 3, 5]
n = len(a)
 
k = 4
 
# Function call
print(sub_arrays(a, n, k))
 
# This code is contributed by Mohit Kumar

// C# implementation of the approach
using System;
using System.Collections.Generic;
 
class gfg
{
    // Function to return the number of subarrays
    // of the given array such that the remainder
    // when dividing the sum of its elements
    // by K is equal to the number of its elements
    static int sub_arrays(int []a, int n, int k)
    {
     
        // To store prefix sum
        int []sum = new int[n + 2] ;
         
        for (int i = 0; i < n + 2; i++)
        {
            sum[i] = 0;
        }
         
        for (int i = 0; i < n; i++)
        {
     
            // We are dealing with zero
            // indexed array
            a[i]--;
     
            // Taking modulus value
            a[i] %= k;
     
            // Prefix sum
            sum[i + 1] += sum[i] + a[i];
            sum[i + 1] %= k;
        }
     
        // To store the required answer, the left
        // index and the right index
        int ans = 0, l = 0, r = 0;
     
        // To store si - i value
        Dictionary<int, int> mp = new Dictionary<int, int>();
     
        for (int i = 0; i < n + 1; i++)
        {
            if(!mp.ContainsKey(sum[i]))
                mp.Add(sum[i], 0);
        }
        int temp;
         
        for (int i = 0; i < n + 1; i++)
        {
     
            // Include sum
            ans += (int)mp[sum[i]];
            temp =(int)mp[sum[i]] + 1;
            mp[sum[i]] = temp;
     
            // Increment the right index
            r++;
     
            // If subarray has at least
            // k elements
            if (r - l >= k)
            {
                //mp[sum[l]]--;
                temp = (int)mp[sum[l]] - 1;
                mp[sum[i]] = temp;
                l++;
            }
        }
     
        // Return the required answer
        return ans;
    }
     
    // Driver code
    public static void Main(String []args)
    {
        int []a = { 1, 4, 2, 3, 5 };
         
        int n = a.Length;
     
        int k = 4;
     
        // Function call
        Console.Write(sub_arrays(a, n, k));
    }
}
 
// This code is contributed by 29AjayKumar

<script>
 
// JavaScript implementation of the approach
 
// Function to return the number of subarrays
// of the given array such that the remainder
// when dividing the sum of its elements
// by K is equal to the number of its elements
function sub_arrays(a, n, k) {
 
    // To store prefix sum
    let sum = new Array(n + 2);
 
    for (let i = 0; i < n + 2; i++) {
        sum[i] = 0;
    }
 
    for (let i = 0; i < n; i++) {
 
        // We are dealing with zero
        // indexed array
        a[i]--;
 
        // Taking modulus value
        a[i] %= k;
 
        // Prefix sum
        sum[i + 1] += sum[i] + a[i];
        sum[i + 1] %= k;
    }
 
    // To store the required answer, the left
    // index and the right index
    let ans = 0, l = 0, r = 0;
 
    // To store si - i value
    let mp = new Map();
 
    for (let i = 0; i < n + 1; i++) {
        if (!mp.has(sum[i]))
            mp.set(sum[i], 0);
    }
    let temp;
 
    for (let i = 0; i < n + 1; i++) {
 
        // Include sum
        ans += mp.get(sum[i]);
        temp = mp.get(sum[i]) + 1;
        mp.set(sum[i], temp);
 
        // Increment the right index
        r++;
 
        // If subarray has at least
        // k elements
        if (r - l >= k) {
            //mp[sum[l]]--;
            temp = mp.get(sum[l]) - 1;
            mp.set(sum[i], temp);
            l++;
        }
    }
 
    // Return the required answer
    return ans;
}
 
// Driver code
 
let a = [1, 4, 2, 3, 5];
 
let n = a.length;
 
let k = 4;
 
// Function call
document.write(sub_arrays(a, n, k));
 
// This code is contributed by _saurabh_jaiswal
 
</script>

Producción:

4

Complejidad de tiempo: O(N* log(N))
Espacio auxiliar: O(N)