quick - Número de subarrays divisibles por k

quick sort complexity

Question

Tuve la siguiente pregunta en una entrevista y, a pesar de que di una implementación funcional, no fue lo suficientemente eficiente.

Una porción de la matriz A es cualquier par de enteros (P, Q) de manera que 0 ≤ P ≤ Q <N. Una porción (P, Q) de la matriz A es divisible por K si el número A [P] + A [P +1] + ... + A [Q − 1] + A [Q] es divisible por K.

La función que me pidieron que escribiera tenía que devolver el número de divisiones divisibles por K. La complejidad del tiempo esperado era O (máx (N, K)) y la complejidad del espacio era O (K).

Mi solución fue la más simple, un bucle dentro de otro y verifico cada porción: O (n ^ 2)

He estado pensando, pero realmente no puedo entender cómo puedo hacerlo en O (máx. (N, K)).

Puede ser una variante del problema de la suma de subconjuntos , pero no sé cómo contar cada subconjunto.

EDITAR: Los elementos en el conjunto podrían ser negativos. Aquí hay un ejemplo:

A = {4, 5, 0, -2, -3, 1}, K = 5

Function must return 7, because there are 7 subarrays which sums are divisible by 5
{4, 5, 0, -2, -3, 1}
{5}
{5, 0}
{5, 0, -2, -3}
{0}
{0, -2, -3}
{-2, -3}

Answer 1

Aquí hay una implementación de Java de la solución propuesta por @Thomash.

El segundo bucle no es necesario, porque podemos aumentar directamente la respuesta por el valor actual y luego incrementarla.

Para evitar un índice de matriz negativo, también tenemos que ajustar el cálculo del módulo.

public static int countSubarrays(int[] nums, int k) {
    int[] cache = new int[k];
    cache[0]++;
    int s = 0, counter = 0;
    for (int i = 0; i < nums.length; i++) {
        s = ((s + nums[i]) % k + k) % k;
        counter += cache[s];
        cache[s]++;
    }

    return counter;
}

Answer 2

Como solo te interesan los números divisibles por K, puedes hacer todos los cálculos en módulo K. Considera la matriz de suma acumulativa S de modo que S [i] = S [0] + S [1] + ... + S [i] . Entonces (P, Q) es un sector divisible por K sif S [P] = S [Q] (recuerda que hacemos todos los cálculos en módulo K). Así que solo tienes que contar para cada valor posible de [0, ..., K-1] cuántas veces aparece en S.

Aquí hay un pseudocódigo:

B = new array(K)
B[0]++
s = 0
for i = 0 to N-1
  s = (s + A[i]) % K
  B[s]++
ans = 0
for i = 0 to K-1
  ans += B[i]*(B[i]-1)/2

Una vez que sepa que son x celdas en S que tienen valor i, desea contar el número de cortes que comienza en una celda con valor i y termina en una celda con valor i, este número es x (x-1) / 2. Para resolver problemas de borde, agregamos una celda con valor 0.

Answer 3

Gracias por tu solución , @damluar, ¡es muy limpio! Solo quiero añadir algunos comentarios.

1. La salida debe ser 7, no 6 como su salida. Debido a que tenemos 7 subarrays que son divisibles por k como se muestra a continuación, agregando res += storedArray[0]; arreglarlo.

{4, 5, 0, -2, -3, 1}; {5}; {5, 0}; {5, 0, -2, -3}; {0}; {0, -2, -3}; {-2, -3}

Enlace de referencia

2. Inicializando cache[0]++; depende del idioma, si se usa C ++, es necesario, pero no es necesario para java [ link ].

Código:

public class HelloWorld{

public static void main(String []args){
    int [] A = new int[] {4,5,0,-2,-3,1};
    int k = 5;
    int ans=0;
    System.out.println(countSubArray(A, k)); // output = 7

}

public static int countSubArray(int [] nums, int k){
    int [] storedArray = new int[k];
    int sum=0, res=0;
    for(int i=0; i<nums.length; i++){
        sum = (((sum + nums[i]) % k) + k) % k;
        res += storedArray[sum];
        storedArray[sum]++;

    }
    res += storedArray[0];
    return res; 
}
}

Answer 4

Para un número dado X ...

La idea básica:

the sum from the first element to b = the sum from the first element to a
                                    + the sum of the elements between the two

Asi que:

the sum of the elements between the two = the sum from the first element to b
                                        - the sum from the first element to a

Luego, si esas sumas a la derecha tienen el mismo resto cuando se dividen por X , los restantes se cancelarán y la suma de los elementos entre los dos será divisible por X Una elaboración:

C = the sum of the elements between the two
B = the sum from the first element to b
A = the sum from the first element to a

Ahora podemos convertir B a la forma PX + Q y A a la forma RX + S , para algunos enteros P , Q , R y S , con 0 <= Q, S < X . Aquí, por definición, Q y S serían los restos respectivos de B y A divididos por X

Entonces nosotros tenemos:

C = (PX + Q) - (RX + S)
C = PX + Q - RX - S
C = PX - RX + Q - S
C = (P-R)X + Q - S

Claramente (PR)X es divisible por X (el resultado es simplemente (PR) ). Ahora solo necesitamos que Q - S sea ​​divisible por X , pero como 0 <= Q, S < X , tendrán que ser iguales.

Ejemplo:

Sea B = 13 , A = 7 , X = 3 .

Aquí B % X = 1 y A % X = 1 .

Podemos reescribir B como 4*3 + 1 y A como 2*3 + 1 .

Entonces C = 4*3 + 1 - 2*3 - 1 = 2*3 , que es divisible por 3 .

Enfoque de alto nivel:

Construya un hash-map que almacenará la suma acumulada de todos los números hasta el momento en el que mod X asignó al conteo de la frecuencia con la que aparece el valor del resto (construido en O(n) esperado).

Aumente el valor de 0 en uno, esto corresponde al inicio de la matriz.

Inicializa una cuenta a 0.

nC2 el hash-map y agregue nC2 (= value!/(2*(value-2)!) ) Al conteo. Los 2 que elegimos aquí son las posiciones inicial y final del subarreglo.

El conteo es el valor deseado.

Tiempo de ejecución:

Se espera O(n) .

Ejemplo:

Input:    0  5  3  8  2  1
X = 3

Sum:   0  0  5  8 16 18 19
Mod 3: 0  0  2  2  1  0  1

Map:
  0 -> 3
  2 -> 2
  1 -> 2

Count = 3! / 2*(3-2)! = 3  +
        2! / 2*(2-2)! = 1  +
        2! / 2*(2-2)! = 1
      = 5

Los subarrays serán:

0  5  3  8  2  1
-                     0                 =  0 % 3 = 0
-------------         0 + 5 + 3 + 8 + 2 = 18 % 3 = 0
   ----------         5 + 3 + 8 + 2     = 18 % 3 = 0
      -               3                 =  3 % 3 = 0
            ----      2 + 1             =  3 % 3 = 0

Answer 5

Ejemplo: -

Matriz de entrada

int [] nums = {4,3,1,2,1,5,2};

K es 3

Suma consecutiva

4,7,8,10,11,16,18

Divide por encima de la matriz de suma consecutiva por 3

1,1,2,1,2,1,0

así que tenemos cuatro 1''s, Two 2''s, one 0''s

por lo que el recuento total será (4 * 3) / 2 + (2 * 1) / 2 + (2 * 1) / 2 = 8

(4 * 3) / 2 viene de seleccionar dos cualquiera de 1 de cada cuatro, es decir, nC2 = n (n-1) / 2

Aquí está el programa

public static long countSubArrayDivByK (int k, int [] nums) {

    Map<Integer, Integer> modulusCountMap = new HashMap<Integer, Integer>();
    int [] consecSum = new int[nums.length];
    consecSum[0]=nums[0];

    for(int i=1;i<nums.length;i++){
        consecSum[i]= consecSum[i-1] +nums[i];
    }

    for(int i=0;i<nums.length;i++){
        consecSum[i]= consecSum[i]%k;

            if(consecSum[i]==0 && modulusCountMap.get(consecSum[i])==null){
                modulusCountMap.put(consecSum[i], 2);
            }else{
                modulusCountMap.put(consecSum[i], modulusCountMap.get(consecSum[i])==null ? 1 : modulusCountMap.get(consecSum[i])+1);
            }

    }

    int count = 0;

    for (Integer val : modulusCountMap.values()) {
        count = count +  (val*(val-1))/2;
    }

    return count;
}

Versión optimizada de arriba

static long customOptimizedCountSubArrayDivByK(int k, int[] nums) {

        Map<Integer, Integer> modulusCountMap = new HashMap<Integer, Integer>();
        int [] quotient = new int[nums.length];
        quotient[0]=nums[0]%3;



        if(quotient[0]==0){
            modulusCountMap.put(quotient[0], 2);
        }else{
            modulusCountMap.put(quotient[0], 1);
        }


        for(int i=1;i<nums.length;i++){
            quotient[i]= (quotient[i-1] + nums[i])%3;


                if(quotient[i]==0 && modulusCountMap.get(quotient[i])==null){
                    modulusCountMap.put(quotient[i], 2);
                }else{
                    modulusCountMap.put(quotient[i], modulusCountMap.get(quotient[i])==null ? 1 : modulusCountMap.get(quotient[i])+1);
                }

        }

        int count = 0;

        for (Integer val : modulusCountMap.values()) {
            count = count +  (val*(val-1))/2;
        }

        return count;
    }

Answer 6

public class SubArrayDivisible 
{

    public static void main(String[] args) 
    {
        int[] A = {4, 5, 0, -2, -3, 1};
        SubArrayDivisible obj = new SubArrayDivisible();
        obj.getSubArrays(A,5);
    }

    private void getSubArrays(int[] A,int K)
    {
        int count = 0,s=0;
        for(int i=0;i<A.length;i++)
        {
            s = 0;
            for(int j = i;j<A.length;j++)
            {
                s = s+A[j];
                if((s%K) == 0)
                {
                    System.out.println("Value of S "+s);
                    count++;
                }

            }
        }
        System.out.println("Num of Sub-Array "+count);
    }
}

Answer 7

    private int GetSubArraysCount(int[] A, int K)
    {
        int N = A.Length;
        int[] B = new int[K];
        for (int i = 0; i < B.Length; i++)
        {
            B[i] = 0;
        }
        B[0]++;
        int s = 0;
        for (int i = 0; i < N; i++)
        {
            s = (s + A[i]) % K;
            while (s < 0)
            {
                s += K;
            }
            B[s]++;
        }
        int ans = 0;
        for (int i = 0; i <= K - 1; i++)
        {
            ans += B[i] * (B[i] - 1) / 2;
        }
        return ans;
    }

Answer 8

static void Main(string[] args)
    {
        int[] A = new int[] { 4, 5, 0, -2, -3, 1 };
        int sum = 0;
        int i, j;
        int count = 0;
        for (i = 0; i < A.Length; i++)
        {
            for (j = 0; j < A.Length; j++)
            {
                if (j + i < 6)
                    sum += A[j + i];
                if ((sum % 5) == 0)
                    count++;

            }
            sum = 0;
        }
        Console.WriteLine(count);
        Console.ReadLine();


    }