Recuento de elementos tales que la diferencia entre la suma de los subconjuntos izquierdo y derecho es igual a un múltiplo de k

Dado un arreglo arr[] de longitud n y un entero k , la tarea es encontrar el número de índices de 2 a n-1 en un arreglo que tiene una diferencia de la suma de los subarreglos izquierdo y derecho igual al múltiplo de el número dado k.

Ejemplos:  

Entrada: arr[] = {1, 2, 3, 3, 1, 1}, k = 4 
Salida: 2 
Explicación: Los únicos índices posibles son 4 y 5

Entrada: arr[] = {1, 2, 3, 4, 5}, k = 1 
Salida: 3  

Acercarse: 

• Cree una array de prefijos que contenga la suma de los elementos a la izquierda y la array de sufijos que contenga la suma de los elementos a la derecha. 
• Comprueba para cada índice la diferencia de la suma de la izquierda y la derecha y aumenta el contador si es divisible por k.

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

// C++ code to count of elements such that
// difference between the sum of left and right
// sub-arrays are equal to a multiple of k
 
#include <bits/stdc++.h>
using namespace std;
 
// Functions to find the no of elements
int noOfElement(int a[], int n, int k)
{
    // Creating a prefix array
    int prefix[n];
 
    // Starting element of prefix array
    // will be the first element
    // of given array
    prefix[0] = a[0];
    for (int i = 1; i < n; i++) {
        prefix[i] = prefix[i - 1] + a[i];
    }
 
    // Creating a suffix array;
    int suffix[n];
    // Last element of suffix array will
    // be the last element of given array
    suffix[n - 1] = a[n - 1];
    for (int i = n - 2; i >= 0; i--) {
        suffix[i] = suffix[i + 1] + a[i];
    }
 
    // Checking difference of left and right half
    // is divisible by k or not.
    int cnt = 0;
    for (int i = 1; i < n - 1; i++) {
        if ((prefix[i] - suffix[i]) % k == 0
            || (suffix[i] - prefix[i]) % k == 0) {
            cnt = cnt + 1;
        }
    }
 
    return cnt;
}
 
// Driver code
int main()
{
    int a[] = { 1, 2, 3, 3, 1, 1 };
    int k = 4;
    int n = sizeof(a) / sizeof(a[0]);
    cout << noOfElement(a, n, k);
    return 0;
}

// Java code to count of elements such that
// difference between the sum of left and right
// sub-arrays are equal to a multiple of k
class GFG
{
 
// Functions to find the no of elements
static int noOfElement(int a[], int n, int k)
{
    // Creating a prefix array
    int []prefix = new int[n];
 
    // Starting element of prefix array
    // will be the first element
    // of given array
    prefix[0] = a[0];
    for (int i = 1; i < n; i++)
    {
        prefix[i] = prefix[i - 1] + a[i];
    }
 
    // Creating a suffix array;
    int []suffix = new int[n];
     
    // Last element of suffix array will
    // be the last element of given array
    suffix[n - 1] = a[n - 1];
    for (int i = n - 2; i >= 0; i--)
    {
        suffix[i] = suffix[i + 1] + a[i];
    }
 
    // Checking difference of left and right half
    // is divisible by k or not.
    int cnt = 0;
    for (int i = 1; i < n - 1; i++)
    {
        if ((prefix[i] - suffix[i]) % k == 0
            || (suffix[i] - prefix[i]) % k == 0)
        {
            cnt = cnt + 1;
        }
    }
    return cnt;
}
 
// Driver code
public static void main(String[] args)
{
    int a[] = { 1, 2, 3, 3, 1, 1 };
    int k = 4;
    int n = a.length;
    System.out.print(noOfElement(a, n, k));
}
}
 
// This code is contributed by Rajput-Ji

# Python3 code to count of elements such that
# difference between the sum of left and right
# sub-arrays are equal to a multiple of k
 
# Functions to find the no of elements
def noOfElement(a, n, k):
     
    # Creating a prefix array
    prefix = [0] * n
 
    # Starting element of prefix array
    # will be the first element
    # of given array
    prefix[0] = a[0]
    for i in range(1, n):
        prefix[i] = prefix[i - 1] + a[i]
 
    # Creating a suffix array
    suffix = [0] * n
     
    # Last element of suffix array will
    # be the last element of given array
    suffix[n - 1] = a[n - 1]
    for i in range(n - 2, -1, -1):
        suffix[i] = suffix[i + 1] + a[i]
 
    # Checking difference of left and right half
    # is divisible by k or not.
    cnt = 0
    for i in range(1, n - 1):
        if ((prefix[i] - suffix[i]) % k == 0 or (suffix[i] - prefix[i]) % k == 0):
            cnt = cnt + 1
 
    return cnt
 
# Driver code
 
a = [ 1, 2, 3, 3, 1, 1 ]
k = 4
n = len(a)
print(noOfElement(a, n, k))
 
# This code is contributed by mohit kumar 29

// C# code to count of elements such that
// difference between the sum of left and right
// sub-arrays are equal to a multiple of k
using System;
 
class GFG
{
 
    // Functions to find the no of elements
    static int noOfElement(int []a, int n, int k)
    {
        // Creating a prefix array
        int []prefix = new int[n];
     
        // Starting element of prefix array
        // will be the first element
        // of given array
        prefix[0] = a[0];
        for (int i = 1; i < n; i++)
        {
            prefix[i] = prefix[i - 1] + a[i];
        }
     
        // Creating a suffix array;
        int []suffix = new int[n];
         
        // Last element of suffix array will
        // be the last element of given array
        suffix[n - 1] = a[n - 1];
        for (int i = n - 2; i >= 0; i--)
        {
            suffix[i] = suffix[i + 1] + a[i];
        }
     
        // Checking difference of left and right half
        // is divisible by k or not.
        int cnt = 0;
        for (int i = 1; i < n - 1; i++)
        {
            if ((prefix[i] - suffix[i]) % k == 0
                || (suffix[i] - prefix[i]) % k == 0)
            {
                cnt = cnt + 1;
            }
        }
        return cnt;
    }
     
    // Driver code
    public static void Main()
    {
        int []a = { 1, 2, 3, 3, 1, 1 };
        int k = 4;
        int n = a.Length;
        Console.Write(noOfElement(a, n, k));
    }
}
 
// This code is contributed by AnkitRai01

<script>
// Javascript code to count of elements such that
// difference between the sum of left and right
// sub-arrays are equal to a multiple of k
     
// Functions to find the no of elements
function noOfElement(a,n,k)
{
    // Creating a prefix array
    let prefix = new Array(n);
   
    // Starting element of prefix array
    // will be the first element
    // of given array
    prefix[0] = a[0];
    for (let i = 1; i < n; i++)
    {
        prefix[i] = prefix[i - 1] + a[i];
    }
   
    // Creating a suffix array;
    let suffix = new Array(n);
       
    // Last element of suffix array will
    // be the last element of given array
    suffix[n - 1] = a[n - 1];
    for (let i = n - 2; i >= 0; i--)
    {
        suffix[i] = suffix[i + 1] + a[i];
    }
   
    // Checking difference of left and right half
    // is divisible by k or not.
    let cnt = 0;
    for (let i = 1; i < n - 1; i++)
    {
        if ((prefix[i] - suffix[i]) % k == 0
            || (suffix[i] - prefix[i]) % k == 0)
        {
            cnt = cnt + 1;
        }
    }
    return cnt;
}
     
    // Driver code   
    let a=[1, 2, 3, 3, 1, 1];
    let k = 4;
    let n = a.length;
    document.write(noOfElement(a, n, k));
       
 
 
// This code is contributed by patel2127
</script>

2

Complejidad de tiempo: O(n), donde n es el tamaño de la array
Espacio auxiliar: O(n), ya que el espacio adicional de tamaño n se usa para crear una array de prefijos y sufijos