Dado un entero K y un arreglo arr[] que consta de N enteros positivos, la tarea es encontrar el número de subarreglos cuya suma módulo K es igual al tamaño del subarreglo.
Ejemplos:
Entrada: arr[] = {1, 4, 3, 2}, K = 3
Salida: 4
Explicación:
1 % 3 = 1
(1 + 4) % 3 = 2
4 % 3 = 1
(3 + 2) % 3 = 2
Por lo tanto, los subarreglos {1}, {1, 4}, {4}, {3, 2} satisfacen las condiciones requeridas.Entrada: arr[] = {2, 3, 5, 3, 1, 5}, K = 4
Salida: 5
Explicación:
Los subarreglos (5), (1), (5), (1, 5), (3 , 5, 3) cumplen la condición requerida.
Enfoque ingenuo: el enfoque más simple es encontrar la suma de prefijos de la array dada, luego generar todos los subarreglos de la array de suma de prefijos y contar esos subarreglos que tienen un módulo de suma K igual a la longitud de ese subarreglo. Imprime el recuento final de subarreglos obtenidos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program of the above approach
#include <bits/stdc++.h>
using namespace std;
// Function that counts the subarrays
// having sum modulo k equal to the
// length of subarray
long long int countSubarrays(
int a[], int n, int k)
{
// Stores the count
// of subarrays
int ans = 0;
// Stores prefix sum
// of the array
vector<int> pref;
pref.push_back(0);
// Calculate prefix sum array
for (int i = 0; i < n; i++)
pref.push_back((a[i]
+ pref[i])
% k);
// Generate all the subarrays
for (int i = 1; i <= n; i++) {
for (int j = i; j <= n; j++) {
// Check if this subarray is
// a valid subarray or not
if ((pref[j] - pref[i - 1] + k) % k
== j - i + 1) {
ans++;
}
}
}
// Total count of subarrays
cout << ans << ' ';
}
// Driver Code
int main()
{
// Given arr[]
int arr[] = { 2, 3, 5, 3, 1, 5 };
// Size of the array
int N = sizeof(arr) / sizeof(arr[0]);
// Given K
int K = 4;
// Function Call
countSubarrays(arr, N, K);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
import java.lang.*;
import java.io.*;
class GFG{
// Function that counts the subarrays
// having sum modulo k equal to the
// length of subarray
static void countSubarrays(int a[], int n,
int k)
{
// Stores the count
// of subarrays
int ans = 0;
// Stores prefix sum
// of the array
ArrayList<Integer> pref = new ArrayList<>();
pref.add(0);
// Calculate prefix sum array
for(int i = 0; i < n; i++)
pref.add((a[i] + pref.get(i)) % k);
// Generate all the subarrays
for(int i = 1; i <= n; i++)
{
for(int j = i; j <= n; j++)
{
// Check if this subarray is
// a valid subarray or not
if ((pref.get(j) -
pref.get(i - 1) + k) %
k == j - i + 1)
{
ans++;
}
}
}
// Total count of subarrays
System.out.println(ans);
}
// Driver Code
public static void main (String[] args)
throws java.lang.Exception
{
// Given arr[]
int arr[] = { 2, 3, 5, 3, 1, 5 };
// Size of the array
int N = arr.length;
// Given K
int K = 4;
// Function call
countSubarrays(arr, N, K);
}
}
// This code is contributed by bikram2001jha
Python3
# Python3 program for the above approach # Function that counts the subarrays # having sum modulo k equal to the # length of subarray def countSubarrays(a, n, k): # Stores the count # of subarrays ans = 0 # Stores prefix sum # of the array pref = [] pref.append(0) # Calculate prefix sum array for i in range(n): pref.append((a[i] + pref[i]) % k) # Generate all the subarrays for i in range(1, n + 1, 1): for j in range(i, n + 1, 1): # Check if this subarray is # a valid subarray or not if ((pref[j] - pref[i - 1] + k) % k == j - i + 1): ans += 1 # Total count of subarrays print(ans, end = ' ') # Driver Code # Given arr[] arr = [ 2, 3, 5, 3, 1, 5 ] # Size of the array N = len(arr) # Given K K = 4 # Function call countSubarrays(arr, N, K) # This code is contributed by sanjoy_62
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function that counts the subarrays
// having sum modulo k equal to the
// length of subarray
static void countSubarrays(int[] a, int n,
int k)
{
// Stores the count
// of subarrays
int ans = 0;
// Stores prefix sum
// of the array
List<int> pref = new List<int>();
pref.Add(0);
// Calculate prefix sum array
for(int i = 0; i < n; i++)
pref.Add((a[i] + pref[i]) % k);
// Generate all the subarrays
for(int i = 1; i <= n; i++)
{
for(int j = i; j <= n; j++)
{
// Check if this subarray is
// a valid subarray or not
if ((pref[j] -
pref[i - 1] + k) %
k == j - i + 1)
{
ans++;
}
}
}
// Total count of subarrays
Console.WriteLine(ans);
}
// Driver Code
public static void Main ()
{
// Given arr[]
int[] arr = { 2, 3, 5, 3, 1, 5 };
// Size of the array
int N = arr.Length;
// Given K
int K = 4;
// Function call
countSubarrays(arr, N, K);
}
}
// This code is contributed by sanjoy_62
Javascript
<script>
// Javascript program of the above approach
// Function that counts the subarrays
// having sum modulo k equal to the
// length of subarray
function countSubarrays( a, n, k)
{
// Stores the count
// of subarrays
var ans = 0;
// Stores prefix sum
// of the array
var pref = [];
pref.push(0);
// Calculate prefix sum array
for (var i = 0; i < n; i++)
pref.push((a[i]
+ pref[i])
% k);
// Generate all the subarrays
for (var i = 1; i <= n; i++) {
for (var j = i; j <= n; j++) {
// Check if this subarray is
// a valid subarray or not
if ((pref[j] - pref[i - 1] + k) % k
== j - i + 1) {
ans++;
}
}
}
// Total count of subarrays
document.write( ans + ' ');
}
// Driver Code
// Given arr[]
var arr = [ 2, 3, 5, 3, 1, 5 ];
// Size of the array
var N = arr.length;
// Given K
var K = 4;
// Function Call
countSubarrays(arr, N, K);
// This code is contributed by itsok.
</script>
Producción:
5
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: la idea es generar la suma de prefijos de la array dada y luego el problema se reduce a la cuenta de subarreglo tal que (pref[j] – pref[i]) % K igual a (j – i) , donde j > i y (j − i) ≤ K. A continuación se muestran los pasos:
- Cree una array auxiliar pref[] que almacene la suma del prefijo de la array dada.
- Para contar el subarreglo que satisface la ecuación anterior, la ecuación se puede escribir como:
(pref[j] − j) % k = (pref[i] − i) % k, donde j > i y (j − i) ≤ K
- Recorra la array de prefijos pref[] y para cada índice j almacene el recuento (pref[j] – j) % K en un mapa M.
- Para cada elemento pref[i] en los pasos anteriores, actualice el conteo como M[(pref[i] – i % K + K) % K] e incremente la frecuencia de (pref[i] – i % K + K) % K en el Mapa M.
- Imprima el valor del recuento de subarreglo después de los pasos anteriores.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program of the above approach
#include <bits/stdc++.h>
using namespace std;
// Function that counts the subarrays
// s.t. sum of elements in the subarray
// modulo k is equal to size of subarray
long long int countSubarrays(
int a[], int n, int k)
{
// Stores the count of (pref[i] - i) % k
unordered_map<int, int> cnt;
// Stores the count of subarray
long long int ans = 0;
// Stores prefix sum of the array
vector<int> pref;
pref.push_back(0);
// Find prefix sum array
for (int i = 0; i < n; i++)
pref.push_back((a[i]
+ pref[i])
% k);
// Base Condition
cnt[0] = 1;
for (int i = 1; i <= n; i++) {
// Remove the index at present
// after K indices from the
// current index
int remIdx = i - k;
if (remIdx >= 0) {
cnt[(pref[remIdx]
- remIdx % k + k)
% k]--;
}
// Update the answer for subarrays
// ending at the i-th index
ans += cnt[(pref[i]
- i % k + k)
% k];
// Add the calculated value of
// current index to count
cnt[(pref[i] - i % k + k) % k]++;
}
// Print the count of subarrays
cout << ans << ' ';
}
// Driver Code
int main()
{
// Given arr[]
int arr[] = { 2, 3, 5, 3, 1, 5 };
// Size of the array
int N = sizeof(arr) / sizeof(arr[0]);
// Given K
int K = 4;
// Function Call
countSubarrays(arr, N, K);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
import java.lang.*;
import java.io.*;
class GFG{
// Function that counts the subarrays
// having sum modulo k equal to the
// length of subarray
static void countSubarrays(int a[], int n,
int k)
{
// Stores the count of (pref[i] - i) % k
HashMap<Integer, Integer> cnt = new HashMap<>();
// Stores the count of subarray
long ans = 0;
// Stores prefix sum of the array
ArrayList<Integer> pref = new ArrayList<>();
pref.add(0);
// Find prefix sum array
for(int i = 0; i < n; i++)
pref.add((a[i] + pref.get(i)) % k);
// Base Condition
cnt.put(0, 1);
for(int i = 1; i <= n; i++)
{
// Remove the index at present
// after K indices from the
// current index
int remIdx = i - k;
if (remIdx >= 0)
{
if (cnt.containsKey((pref.get(remIdx) -
remIdx % k + k) % k))
cnt.put((pref.get(remIdx) -
remIdx % k + k) % k,
cnt.get((pref.get(remIdx) -
remIdx % k + k) % k) - 1);
else
cnt.put((pref.get(remIdx) -
remIdx % k + k) % k, -1);
}
// Update the answer for subarrays
// ending at the i-th index
if (cnt.containsKey((pref.get(i) -
i % k + k) % k))
ans += cnt.get((pref.get(i) -
i % k + k) % k);
// Add the calculated value of
// current index to count
if (cnt.containsKey((pref.get(i) -
i % k + k) % k))
cnt.put((pref.get(i) -
i % k + k) % k,
cnt.get((pref.get(i) -
i % k + k) % k) + 1);
else
cnt.put((pref.get(i) -
i % k + k) % k, 1);
}
// Print the count of subarrays
System.out.println(ans);
}
// Driver Code
public static void main (String[] args)
throws java.lang.Exception
{
// Given arr[]
int arr[] = { 2, 3, 5, 3, 1, 5 };
// Size of the array
int N = arr.length;
// Given K
int K = 4;
// Function call
countSubarrays(arr, N, K);
}
}
// This code is contributed by bikram2001jha
Python3
# Python3 program of the above approach
# Function that counts the subarrays
# s.t. sum of elements in the subarray
# modulo k is equal to size of subarray
def countSubarrays(a, n, k):
# Stores the count of (pref[i] - i) % k
cnt = {}
# Stores the count of subarray
ans = 0
# Stores prefix sum of the array
pref = []
pref.append(0)
# Find prefix sum array
for i in range(n):
pref.append((a[i] + pref[i]) % k)
# Base Condition
cnt[0] = 1
for i in range(1, n + 1):
# Remove the index at present
# after K indices from the
# current index
remIdx = i - k
if (remIdx >= 0):
if ((pref[remIdx] -
remIdx % k + k) % k in cnt):
cnt[(pref[remIdx] -
remIdx % k + k) % k] -= 1
else:
cnt[(pref[remIdx] -
remIdx % k + k) % k] = -1
# Update the answer for subarrays
# ending at the i-th index
if (pref[i] - i % k + k) % k in cnt:
ans += cnt[(pref[i] - i % k + k) % k]
# Add the calculated value of
# current index to count
if (pref[i] - i % k + k) % k in cnt:
cnt[(pref[i] - i % k + k) % k] += 1
else:
cnt[(pref[i] - i % k + k) % k] = 1
# Print the count of subarrays
print(ans, end = ' ')
# Driver code
# Given arr[]
arr = [ 2, 3, 5, 3, 1, 5 ]
# Size of the array
N = len(arr)
# Given K
K = 4
# Function call
countSubarrays(arr, N, K)
# This code is contributed by divyeshrabadiya07
C#
// C# program for
// the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function that counts the subarrays
// having sum modulo k equal to the
// length of subarray
static void countSubarrays(int []a, int n,
int k)
{
// Stores the count of
// (pref[i] - i) % k
Dictionary<int,
int> cnt = new Dictionary<int,
int>();
// Stores the count of subarray
long ans = 0;
// Stores prefix sum of the array
List<int> pref = new List<int>();
pref.Add(0);
// Find prefix sum array
for(int i = 0; i < n; i++)
pref.Add((a[i] + pref[i]) % k);
// Base Condition
cnt.Add(0, 1);
for(int i = 1; i <= n; i++)
{
// Remove the index at present
// after K indices from the
// current index
int remIdx = i - k;
if (remIdx >= 0)
{
if (cnt.ContainsKey((pref[remIdx] -
remIdx % k + k) % k))
cnt[(pref[remIdx] -
remIdx % k + k) % k] = cnt[(pref[remIdx] -
remIdx % k + k) % k] - 1;
else
cnt.Add((pref[remIdx] -
remIdx % k + k) % k, -1);
}
// Update the answer for subarrays
// ending at the i-th index
if (cnt.ContainsKey((pref[i] -
i % k + k) % k))
ans += cnt[(pref[i] -
i % k + k) % k];
// Add the calculated value of
// current index to count
if (cnt.ContainsKey((pref[i] -
i % k + k) % k))
cnt[(pref[i] -
i % k + k) % k] = cnt[(pref[i] -
i % k + k) % k] + 1;
else
cnt.Add((pref[i] -
i % k + k) % k, 1);
}
// Print the count of subarrays
Console.WriteLine(ans);
}
// Driver Code
public static void Main(String[] args)
{
// Given []arr
int []arr = {2, 3, 5, 3, 1, 5};
// Size of the array
int N = arr.Length;
// Given K
int K = 4;
// Function call
countSubarrays(arr, N, K);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// javascript program for the above approach
// Function that counts the subarrays
// having sum modulo k equal to the
// length of subarray
function countSubarrays(a , n , k) {
// Stores the count of (pref[i] - i) % k
var cnt = new Map();
// Stores the count of subarray
var ans = 0;
// Stores prefix sum of the array
var pref = [];
pref.push(0);
// Find prefix sum array
for (i = 0; i < n; i++)
pref.push((a[i] + pref[i]) % k);
// Base Condition
cnt.set(0, 1);
for (i = 1; i <= n; i++) {
// Remove the index at present
// after K indices from the
// current index
var remIdx = i - k;
if (remIdx >= 0) {
if (cnt.has((pref[remIdx] - remIdx % k + k) % k))
cnt.set((pref[remIdx] - remIdx % k + k) % k,
cnt.get((pref[remIdx] - remIdx % k + k) % k) - 1);
else
cnt.set((pref.get(remIdx) - remIdx % k + k) % k, -1);
}
// Update the answer for subarrays
// ending at the i-th index
if (cnt.has((pref[i] - i % k + k) % k))
ans += cnt.get((pref[i] - i % k + k) % k);
// Add the calculated value of
// current index to count
if (cnt.has((pref[i] - i % k + k) % k))
cnt.set((pref[i] - i % k + k) % k, cnt.get((pref[i] - i % k + k) % k) + 1);
else
cnt.set((pref[i] - i % k + k) % k, 1);
}
// Print the count of subarrays
document.write(ans);
}
// Driver Code
// Given arr
var arr = [ 2, 3, 5, 3, 1, 5 ];
// Size of the array
var N = arr.length;
// Given K
var K = 4;
// Function call
countSubarrays(arr, N, K);
// This code is contributed by umadevi9616
</script>
Producción:
5
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por lostsoul27 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA