Se le proporciona una array de enteros positivos y/o negativos y un valor K . ¿La tarea es encontrar el recuento de todos los subconjuntos cuya suma es divisible por K?
Ejemplos:
Input : arr[] = {4, 5, 0, -2, -3, 1},
K = 5
Output : 7
// there are 7 sub-arrays whose sum is divisible by K
// {4, 5, 0, -2, -3, 1}
// {5}
// {5, 0}
// {5, 0, -2, -3}
// {0}
// {0, -2, -3}
// {-2, -3}
Una solución simple para este problema es calcular uno por uno la suma de todos los subconjuntos posibles y verificar el divisible por K. La complejidad de tiempo para este enfoque será O (n ^ 2).
Una solución eficiente se basa en la siguiente observación.
Let there be a subarray (i, j) whose sum is divisible by k
sum(i, j) = sum(0, j) - sum(0, i-1)
Sum for any subarray can be written as q*k + rem where q
is a quotient and rem is remainder
Thus,
sum(i, j) = (q1 * k + rem1) - (q2 * k + rem2)
sum(i, j) = (q1 - q2)k + rem1-rem2
We see, for sum(i, j) i.e. for sum of any subarray to be
divisible by k, the RHS should also be divisible by k.
(q1 - q2)k is obviously divisible by k, for (rem1-rem2) to
follow the same, rem1 = rem2 where
rem1 = Sum of subarray (0, j) % k
rem2 = Sum of subarray (0, i-1) % k
Entonces, si cualquier suma de subarreglo desde el índice i’th hasta el j’th es divisible por k, entonces podemos decir a[0]+…a[i-1] (mod k) = a[0]+…+a[ j] (mod k)
La explicación anterior es proporcionada por Ekta Goel.
Entonces necesitamos encontrar un par de índices (i, j) que satisfagan la condición anterior.
Aquí está el algoritmo:
- Cree una array auxiliar de tamaño k como Mod[k] . Esta array contiene el recuento de cada resto que obtenemos después de dividir la suma acumulada hasta cualquier índice en arr[].
- Ahora comience a calcular la suma acumulativa y simultáneamente tome su mod con K, cualquier resto que obtengamos incremente el conteo en 1 para el resto como índice en la array auxiliar Mod[]. Sub-arreglo por cada par de posiciones con el mismo valor de (cumSum % k) constituyen un rango continuo cuya suma es divisible por K.
- Ahora recorra la array auxiliar Mod[], para cualquier Mod[i] > 1 podemos elegir cualquier par de índices para la sub-array por (Mod[i]*(Mod[i] – 1))/2 número de formas. Haz lo mismo para todos los residuos < k y suma el resultado que será el número de todos los subconjuntos posibles divisibles por K.
Implementación:
C++
// C++ program to find count of subarrays with
// sum divisible by k.
#include <bits/stdc++.h>
using namespace std;
// Handles all the cases
// function to find all sub-arrays divisible by k
// modified to handle negative numbers as well
int subCount(int arr[], int n, int k)
{
// create auxiliary hash array to count frequency
// of remainders
int mod[k];
memset(mod, 0, sizeof(mod));
// Traverse original array and compute cumulative
// sum take remainder of this current cumulative
// sum and increase count by 1 for this remainder
// in mod[] array
int cumSum = 0;
for (int i = 0; i < n; i++) {
cumSum += arr[i];
// as the sum can be negative, taking modulo twice
mod[((cumSum % k) + k) % k]++;
}
int result = 0; // Initialize result
// Traverse mod[]
for (int i = 0; i < k; i++)
// If there are more than one prefix subarrays
// with a particular mod value.
if (mod[i] > 1)
result += (mod[i] * (mod[i] - 1)) / 2;
// add the elements which are divisible by k itself
// i.e., the elements whose sum = 0
result += mod[0];
return result;
}
// Driver program to run the case
int main()
{
int arr[] = { 4, 5, 0, -2, -3, 1 };
int k = 5;
int n = sizeof(arr) / sizeof(arr[0]);
cout << subCount(arr, n, k) << endl;
int arr1[] = { 4, 5, 0, -12, -23, 1 };
int k1 = 5;
int n1 = sizeof(arr1) / sizeof(arr1[0]);
cout << subCount(arr1, n1, k1) << endl;
return 0;
}
// This code is corrected by Ashutosh Kumar
Java
// Java program to find count of
// subarrays with sum divisible by k.
import java.util.*;
class GFG {
// Handles all the cases
// function to find all sub-arrays divisible by k
// modified to handle negative numbers as well
static int subCount(int arr[], int n, int k)
{
// create auxiliary hash array to
// count frequency of remainders
int mod[] = new int[k];
Arrays.fill(mod, 0);
// Traverse original array and compute cumulative
// sum take remainder of this current cumulative
// sum and increase count by 1 for this remainder
// in mod[] array
int cumSum = 0;
for (int i = 0; i < n; i++) {
cumSum += arr[i];
// as the sum can be negative, taking modulo twice
mod[((cumSum % k) + k) % k]++;
}
// Initialize result
int result = 0;
// Traverse mod[]
for (int i = 0; i < k; i++)
// If there are more than one prefix subarrays
// with a particular mod value.
if (mod[i] > 1)
result += (mod[i] * (mod[i] - 1)) / 2;
// add the elements which are divisible by k itself
// i.e., the elements whose sum = 0
result += mod[0];
return result;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 4, 5, 0, -2, -3, 1 };
int k = 5;
int n = arr.length;
System.out.println(subCount(arr, n, k));
int arr1[] = { 4, 5, 0, -12, -23, 1 };
int k1 = 5;
int n1 = arr1.length;
System.out.println(subCount(arr1, n1, k1));
}
}
// This code is contributed by Anant Agarwal.
Python3
# Python program to find # count of subarrays with # sum divisible by k. # Handles all the cases # function to find all # sub-arrays divisible by k # modified to handle # negative numbers as well def subCount(arr, n, k): # create auxiliary hash # array to count frequency # of remainders mod =[] for i in range(k + 1): mod.append(0) # Traverse original array # and compute cumulative # sum take remainder of this # current cumulative # sum and increase count by # 1 for this remainder # in mod[] array cumSum = 0 for i in range(n): cumSum = cumSum + arr[i] # as the sum can be negative, # taking modulo twice mod[((cumSum % k)+k)% k]= mod[((cumSum % k)+k)% k] + 1 result = 0 # Initialize result # Traverse mod[] for i in range(k): # If there are more than # one prefix subarrays # with a particular mod value. if (mod[i] > 1): result = result + (mod[i]*(mod[i]-1))//2 # add the elements which # are divisible by k itself # i.e., the elements whose sum = 0 result = result + mod[0] return result # driver code arr = [4, 5, 0, -2, -3, 1] k = 5 n = len(arr) print(subCount(arr, n, k)) arr1 = [4, 5, 0, -12, -23, 1] k1 = 5 n1 = len(arr1) print(subCount(arr1, n1, k1)) # This code is contributed # by Anant Agarwal.
C#
// C# program to find count of
// subarrays with sum divisible by k.
using System;
class GFG {
// Handles all the cases
// function to find all sub-arrays divisible by k
// modified to handle negative numbers as well
static int subCount(int[] arr, int n, int k)
{
// create auxiliary hash array to
// count frequency of remainders
int[] mod = new int[k];
// Traverse original array and compute cumulative
// sum take remainder of this current cumulative
// sum and increase count by 1 for this remainder
// in mod[] array
int cumSum = 0;
for (int i = 0; i < n; i++) {
cumSum += arr[i];
// as the sum can be negative, taking modulo twice
mod[((cumSum % k) + k) % k]++;
}
// Initialize result
int result = 0;
// Traverse mod[]
for (int i = 0; i < k; i++)
// If there are more than one prefix subarrays
// with a particular mod value.
if (mod[i] > 1)
result += (mod[i] * (mod[i] - 1)) / 2;
// add the elements which are divisible by k itself
// i.e., the elements whose sum = 0
result += mod[0];
return result;
}
// Driver code
public static void Main()
{
int[] arr = { 4, 5, 0, -2, -3, 1 };
int k = 5;
int n = arr.Length;
Console.WriteLine(subCount(arr, n, k));
int[] arr1 = { 4, 5, 0, -12, -23, 1 };
int k1 = 5;
int n1 = arr1.Length;
Console.WriteLine(subCount(arr1, n1, k1));
}
}
// This code is contributed by vt_m.
Javascript
<script>
// Javascript program to find count of
// subarrays with sum divisible by k.
// Handles all the cases
// function to find all sub-arrays divisible by k
// modified to handle negative numbers as well
function subCount(arr, n, k)
{
// create auxiliary hash array to
// count frequency of remainders
let mod = new Array(k);
mod.fill(0);
// Traverse original array and compute cumulative
// sum take remainder of this current cumulative
// sum and increase count by 1 for this remainder
// in mod[] array
let cumSum = 0;
for (let i = 0; i < n; i++) {
cumSum += arr[i];
// as the sum can be negative, taking modulo twice
mod[((cumSum % k) + k) % k]++;
}
// Initialize result
let result = 0;
// Traverse mod[]
for (let i = 0; i < k; i++)
// If there are more than one prefix subarrays
// with a particular mod value.
if (mod[i] > 1)
result += parseInt((mod[i] * (mod[i] - 1)) / 2, 10);
// add the elements which are divisible by k itself
// i.e., the elements whose sum = 0
result += mod[0];
return result;
}
let arr = [ 4, 5, 0, -2, -3, 1 ];
let k = 5;
let n = arr.length;
document.write(subCount(arr, n, k) + "</br>");
let arr1 = [ 4, 5, 0, -12, -23, 1 ];
let k1 = 5;
let n1 = arr1.length;
document.write(subCount(arr1, n1, k1));
</script>
Producción
7 7
Complejidad temporal : O(n + k)
Espacio auxiliar : O(k)
Este artículo es una contribución de Shashank Mishra (Gullu) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA