Dada una array, encuentre el número de subarreglos cuya suma es par.
Ejemplo :
Input : arr[] = {1, 2, 2, 3, 4, 1}
Output : 9
There are possible subarrays with even
sum. The subarrays are
1) {1, 2, 2, 3} Sum = 8
2) {1, 2, 2, 3, 4} Sum = 12
3) {2} Sum = 2 (At index 1)
4) {2, 2} Sum = 4
5) {2, 2, 3, 4, 1} Sum = 12
6) {2} Sum = 2 (At index 2)
7) {2, 3, 4, 1} Sum = 10
8) {3, 4, 1} Sum = 8
9) {4} Sum = 4
Método O(n 2 ) tiempo y O(1) espacio [Fuerza bruta]
Simplemente podemos generar todos los subarreglos posibles y encontrar si la suma de todos los elementos en ellos es par o no. Si es par, contaremos ese subarreglo; de lo contrario, lo descartaremos.
Implementación:
C++
/* C++ program to count number of sub-arrays
whose sum is even using brute force
Time Complexity - O(N^2)
Space Complexity - O(1) */
#include<iostream>
using namespace std;
int countEvenSum(int arr[], int n)
{
int result = 0;
// Find sum of all subarrays and increment
// result if sum is even
for (int i=0; i<=n-1; i++)
{
int sum = 0;
for (int j=i; j<=n-1; j++)
{
sum = sum + arr[j];
if (sum % 2 == 0)
result++;
}
}
return (result);
}
// Driver code
int main()
{
int arr[] = {1, 2, 2, 3, 4, 1};
int n = sizeof (arr) / sizeof (arr[0]);
cout << "The Number of Subarrays with even"
" sum is " << countEvenSum (arr, n);
return (0);
}
Java
// Java program to count number
// of sub-arrays whose sum is
// even using brute force
// Time Complexity - O(N^2)
// Space Complexity - O(1)
import java.io.*;
class GFG
{
static int countEvenSum(int arr[],
int n)
{
int result = 0;
// Find sum of all subarrays
// and increment result if
// sum is even
for (int i = 0; i <= n - 1; i++)
{
int sum = 0;
for (int j = i; j <= n - 1; j++)
{
sum = sum + arr[j];
if (sum % 2 == 0)
result++;
}
}
return (result);
}
// Driver code
public static void main (String[] args)
{
int arr[] = {1, 2, 2,
3, 4, 1};
int n = arr.length;
System.out.print("The Number of Subarrays"+
" with even sum is ");
System.out.println(countEvenSum(arr, n));
}
}
// This code is contributed by ajit
Python3
# Python 3 program to count number
# of sub-arrays whose sum is even
# using brute force
# Time Complexity - O(N^2)
# Space Complexity - O(1)
def countEvenSum(arr, n):
result = 0
# Find sum of all subarrays and
# increment result if sum is even
for i in range(0, n, 1):
sum = 0
for j in range(i, n, 1):
sum = sum + arr[j]
if (sum % 2 == 0):
result = result + 1
return (result)
# Driver code
if __name__ == '__main__':
arr = [1, 2, 2, 3, 4, 1]
n = len(arr)
print("The Number of Subarrays" ,
"with even sum is",
countEvenSum (arr, n))
# This code is contributed by
# Surendra_Gangwar
C#
// C# program to count number
// of sub-arrays whose sum is
// even using brute force
// Time Complexity - O(N^2)
// Space Complexity - O(1)
using System;
class GFG
{
static int countEvenSum(int []arr,
int n)
{
int result = 0;
// Find sum of all subarrays
// and increment result if
// sum is even
for (int i = 0; i <= n - 1; i++)
{
int sum = 0;
for (int j = i; j <= n - 1; j++)
{
sum = sum + arr[j];
if (sum % 2 == 0)
result++;
}
}
return (result);
}
// Driver code
static public void Main ()
{
int []arr = {1, 2, 2,
3, 4, 1};
int n = arr.Length;
Console.Write("The Number of Subarrays"+
" with even sum is ");
Console.WriteLine(countEvenSum(arr, n));
}
}
// This code is contributed by m_kit
PHP
<?php
// PHP program to count number
// of sub-arrays whose sum is
// even using brute force
// Time Complexity - O(N^2)
// Space Complexity - O(1)
function countEvenSum($arr, $n)
{
$result = 0;
// Find sum of all subarrays
// and increment result if
// sum is even
for ($i = 0; $i <= $n - 1; $i++)
{
$sum = 0;
for ($j = $i; $j <= $n - 1; $j++)
{
$sum = $sum + $arr[$j];
if ($sum % 2 == 0)
$result++;
}
}
return ($result);
}
// Driver code
$arr = array(1, 2, 2, 3, 4, 1);
$n = sizeof ($arr);
echo "The Number of Subarrays ",
"with even sum is " ,
countEvenSum ($arr, $n);
// This code is contributed by ajit
?>
Javascript
<script>
// Javascript program to count number
// of sub-arrays whose sum is
// even using brute force
// Time Complexity - O(N^2)
// Space Complexity - O(1)
function countEvenSum(arr,
n)
{
let result = 0;
// Find sum of all subarrays
// and increment result if
// sum is even
for (let i = 0; i <= n - 1; i++)
{
let sum = 0;
for (let j = i; j <= n - 1; j++)
{
sum = sum + arr[j];
if (sum % 2 == 0)
result++;
}
}
return (result);
}
// Driver Code
let arr = [1, 2, 2,
3, 4, 1];
let n = arr.length;
document.write("The Number of Subarrays"+
" with even sum is ");
document.write(countEvenSum(arr, n));
</script>
Producción
The Number of Subarrays with even sum is 9
Complejidad temporal: O(n 2 )
Espacio Auxiliar: O(1)
Método O(n) Tiempo y O(1) Espacio [Eficiente]
Si calculamos la array de suma acumulativa en temp[] de nuestra array de entrada, entonces podemos ver que la sub-array que comienza en i y termina en j, tiene una suma uniforme si temp[] si (temp[j] – temp [i]) % 2 = 0. Por lo tanto, en lugar de construir una array de suma acumulativa, construimos una array de módulo 2 de suma acumulativa, y encontramos cuántas veces aparece 0 y 1 en la array temp[] usando la fórmula de protocolo de enlace. [n * (n-1) /2]
Implementación:
C++
/* C++ program to count number of sub-arrays
with even sum using an efficient algorithm
Time Complexity - O(N)
Space Complexity - O(1)*/
#include<iostream>
using namespace std;
int countEvenSum(int arr[], int n)
{
// A temporary array of size 2. temp[0] is
// going to store count of even subarrays
// and temp[1] count of odd.
// temp[0] is initialized as 1 because there
// a single even element is also counted as
// a subarray
int temp[2] = {1, 0};
// Initialize count. sum is sum of elements
// under modulo 2 and ending with arr[i].
int result = 0, sum = 0;
// i'th iteration computes sum of arr[0..i]
// under modulo 2 and increments even/odd count
// according to sum's value
for (int i=0; i<=n-1; i++)
{
// 2 is added to handle negative numbers
sum = ( (sum + arr[i]) % 2 + 2) % 2;
// Increment even/odd count
temp[sum]++;
}
// Use handshake lemma to count even subarrays
// (Note that an even can be formed by two even
// or two odd)
result = result + (temp[0]*(temp[0]-1)/2);
result = result + (temp[1]*(temp[1]-1)/2);
return (result);
}
// Driver code
int main()
{
int arr[] = {1, 2, 2, 3, 4, 1};
int n = sizeof (arr) / sizeof (arr[0]);
cout << "The Number of Subarrays with even"
" sum is " << countEvenSum (arr, n);
return (0);
}
Java
// Java program to count
// number of sub-arrays
// with even sum using an
// efficient algorithm
// Time Complexity - O(N)
// Space Complexity - O(1)
import java.io.*;
class GFG
{
static int countEvenSum(int arr[],
int n)
{
// A temporary array of size 2.
// temp[0] is going to store
// count of even subarrays
// and temp[1] count of odd.
// temp[0] is initialized as
// 1 because there a single even
// element is also counted as
// a subarray
int temp[] = {1, 0};
// Initialize count. sum is
// sum of elements under modulo
// 2 and ending with arr[i].
int result = 0, sum = 0;
// i'th iteration computes sum
// of arr[0..i] under modulo 2
// and increments even/odd count
// according to sum's value
for (int i = 0; i <= n - 1; i++)
{
// 2 is added to handle
// negative numbers
sum = ((sum + arr[i]) %
2 + 2) % 2;
// Increment even/odd count
temp[sum]++;
}
// Use handshake lemma to
// count even subarrays
// (Note that an even can
// be formed by two even
// or two odd)
result = result + (temp[0] *
(temp[0] - 1) / 2);
result = result + (temp[1] *
(temp[1] - 1) / 2);
return (result);
}
// Driver code
public static void main (String[] args)
{
int arr[] = {1, 2, 2, 3, 4, 1};
int n = arr.length;
System.out.println("The Number of Subarrays"+
" with even sum is " +
countEvenSum (arr, n));
}
}
// This code is contributed by ajit
Python 3
# Python 3 program to count number of sub-arrays # with even sum using an efficient algorithm # Time Complexity - O(N) # Space Complexity - O(1) def countEvenSum(arr, n): # A temporary array of size 2. temp[0] is # going to store count of even subarrays # and temp[1] count of odd. # temp[0] is initialized as 1 because there # a single even element is also counted as # a subarray temp = [1, 0] # Initialize count. sum is sum of elements # under modulo 2 and ending with arr[i]. result = 0 sum = 0 # i'th iteration computes sum of arr[0..i] # under modulo 2 and increments even/odd # count according to sum's value for i in range( n): # 2 is added to handle negative numbers sum = ( (sum + arr[i]) % 2 + 2) % 2 # Increment even/odd count temp[sum]+= 1 # Use handshake lemma to count even subarrays # (Note that an even can be formed by two even # or two odd) result = result + (temp[0] * (temp[0] - 1) // 2) result = result + (temp[1] * (temp[1] - 1) // 2) return (result) # Driver code if __name__ == "__main__": arr = [1, 2, 2, 3, 4, 1] n = len(arr) print( "The Number of Subarrays with even" " sum is" , countEvenSum (arr, n)) # This code is contributed by ita_c
C#
// C# program to count
// number of sub-arrays
// with even sum using an
// efficient algorithm
// Time Complexity - O(N)
// Space Complexity - O(1)
using System;
class GFG
{
static int countEvenSum(int []arr,
int n)
{
// A temporary array of size 2.
// temp[0] is going to store
// count of even subarrays
// and temp[1] count of odd.
// temp[0] is initialized as
// 1 because there a single even
// element is also counted as
// a subarray
int []temp = {1, 0};
// Initialize count. sum is
// sum of elements under modulo
// 2 and ending with arr[i].
int result = 0, sum = 0;
// i'th iteration computes sum
// of arr[0..i] under modulo 2
// and increments even/odd count
// according to sum's value
for (int i = 0; i <= n - 1; i++)
{
// 2 is added to handle
// negative numbers
sum = ((sum + arr[i]) %
2 + 2) % 2;
// Increment even
// or odd count
temp[sum]++;
}
// Use handshake lemma to
// count even subarrays
// (Note that an even can
// be formed by two even
// or two odd)
result = result + (temp[0] *
(temp[0] - 1) / 2);
result = result + (temp[1] *
(temp[1] - 1) / 2);
return (result);
}
// Driver code
static public void Main ()
{
int []arr = {1, 2, 2, 3, 4, 1};
int n = arr.Length;
Console.WriteLine("The Number of Subarrays"+
" with even sum is " +
countEvenSum (arr, n));
}
}
// This code is contributed
// by akt_mit
PHP
<?php
// PHP program to count number
// of sub-arrays with even sum
// using an efficient algorithm
// Time Complexity - O(N)
// Space Complexity - O(1)*/
function countEvenSum($arr, $n)
{
// A temporary array of size 2.
// temp[0] is going to store
// count of even subarrays and
// temp[1] count of odd. temp[0]
// is initialized as 1 because
// there a single even element
// is also counted as a subarray
$temp = array(1, 0);
// Initialize count. sum is
// sum of elements under
// modulo 2 and ending with arr[i].
$result = 0; $sum = 0;
// i'th iteration computes
// sum of arr[0..i] under
// modulo 2 and increments
// even/odd count according
// to sum's value
for ($i = 0; $i <= $n - 1; $i++)
{
// 2 is added to handle
// negative numbers
$sum = (($sum + $arr[$i]) %
2 + 2) % 2;
// Increment even/odd
// count
$temp[$sum]++;
}
// Use handshake lemma to
// count even subarrays
// (Note that an even can
// be formed by two even
// or two odd)
$result = $result + (int)($temp[0] *
($temp[0] - 1) / 2);
$result = $result + (int)($temp[1] *
($temp[1] - 1) / 2);
return ($result);
}
// Driver code
$arr = array (1, 2, 2,
3, 4, 1);
$n = sizeof ($arr);
echo "The Number of Subarrays " .
"with even", " sum is " ,
countEvenSum ($arr, $n);
// This code is contributed by ajit
?>
Javascript
<script>
// Javascript program to count
// number of sub-arrays
// with even sum using an
// efficient algorithm
// Time Complexity - O(N)
// Space Complexity - O(1)
function countEvenSum(arr,n)
{
// A temporary array of size 2.
// temp[0] is going to store
// count of even subarrays
// and temp[1] count of odd.
// temp[0] is initialized as
// 1 because there a single even
// element is also counted as
// a subarray
let temp = [1, 0];
// Initialize count. sum is
// sum of elements under modulo
// 2 and ending with arr[i].
let result = 0, sum = 0;
// i'th iteration computes sum
// of arr[0..i] under modulo 2
// and increments even/odd count
// according to sum's value
for (let i = 0; i <= n - 1; i++)
{
// 2 is added to handle
// negative numbers
sum = ((sum + arr[i]) %
2 + 2) % 2;
// Increment even/odd count
temp[sum]++;
}
// Use handshake lemma to
// count even subarrays
// (Note that an even can
// be formed by two even
// or two odd)
result = result + (temp[0] *
(temp[0] - 1) / 2);
result = result + (temp[1] *
(temp[1] - 1) / 2);
return (result);
}
// Driver code
let arr=[1, 2, 2, 3, 4, 1];
let n = arr.length;
document.write("The Number of Subarrays"+
" with even sum is " +
countEvenSum (arr, n));
// This code is contributed by rag2127
</script>
Producción
The Number of Subarrays with even sum is 9
Complejidad de tiempo: O(n)
Espacio Auxiliar: O(1)
Método O(n) Tiempo y O(1) Espacio (enfoque de abajo hacia arriba)
Si comenzamos a contar desde el último índice y hacemos un seguimiento del número de subarreglos con una suma par hasta el momento a partir del índice actual, entonces podemos calcular el número de subarreglos con una suma par a partir del índice anterior
Implementación:
C++
/* C++ program to count number of sub-arrays
with even sum using an efficient algorithm
Time Complexity - O(N)
Space Complexity - O(1)*/
#include <iostream>
using namespace std;
long long countEvenSum(int a[], int n)
{
// Result may be large enough not to
// fit in int;
long long res = 0;
// To keep track of subarrays with even sum
// starting from index i;
int s = 0;
for (int i = n - 1; i >= 0; i--)
{
if (a[i] % 2 == 1)
{
/* s is the count of subarrays starting from
* index i+1 whose sum was even*/
/*
If a[i] is odd then all subarrays starting from
index i+1 which was odd becomes even when a[i]
gets added to it.
*/
s = n - i - 1 - s;
}
else
{
/*
If a[i] is even then all subarrays starting from
index i+1 which was even remains even and one
extra a[i] even subarray gets added to it.
*/
s = s + 1;
}
res = res + s;
}
return res;
}
// Driver Code
int main()
{
int arr[] = { 1, 2, 2, 3, 4, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "The Number of Subarrays with even"
" sum is "
<< countEvenSum(arr, n);
return 0;
}
// This code is contributed by Aditya Anand
Java
// Java program to count
// number of sub-arrays
// with even sum using an
// efficient algorithm
// Time Complexity - O(N)
// Space Complexity - O(1)
import java.io.*;
class GFG {
public static long countEvenSum(int a[], int n)
{
// result may be large enough not to
// fit in int;
long res = 0;
// to keep track of subarrays with even
// sum starting from index i
int s = 0;
for (int i = n - 1; i >= 0; i--)
{
if (a[i] % 2 == 1)
{
// s is the count of subarrays starting from
// index i+1 whose sum was even
/*if a[i] is odd then all subarrays starting
from index i+1 which was odd becomeseven
when a[i] gets added to it.*/
s = n - i - 1 - s;
}
else
{
/*if a[i] is even then all subarrays
starting from index i+1 which was even remainseven
and one extra a[i] even subarray gets added to it.*/
s = s + 1;
}
res = res + s;
}
return res;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 1, 2, 2, 3, 4, 1 };
int n = arr.length;
System.out.println("The Number of Subarrays"
+ " with even sum is "
+ countEvenSum(arr, n));
}
}
// This code is contributed by Aditya Anand
Python3
# Python 3 program to count number of sub-arrays
# with even sum using an efficient algorithm
# Time Complexity - O(N)
# Space Complexity - O(1)
def countEvenSum(arr, n):
# result may be large
# enough not to fit in int;
res = 0
# to keep track of subarrays
# with even sum starting from index i
s = 0
for i in reversed(range(n)):
if arr[i] % 2 == 1:
# s is the count of subarrays
# starting from index i+1
# whose sum was even
"""
if a[i] is odd then all subarrays
starting from index i+1 which was
odd becomes even when a[i] gets
added to it.
"""
s = n-i-1-s
else:
"""
if a[i] is even then all subarrays
starting from index i+1 which was
even remains even and one extra a[i]
even subarray gets added to it.
"""
s = s+1
res = res + s
return res
# Driver code
if __name__ == "__main__":
arr = [1, 2, 2, 3, 4, 1]
n = len(arr)
print("The Number of Subarrays with even"
" sum is", countEvenSum(arr, n))
# This code is contributed by Aditya Anand
C#
// C# program to count
// number of sub-arrays
// with even sum using an
// efficient algorithm
// Time Complexity - O(N)
// Space Complexity - O(1)
using System;
public class GFG
{
public static long countEvenSum(int[] a, int n)
{
// result may be large enough not to
// fit in int;
long res = 0;
// to keep track of subarrays with even
// sum starting from index i
int s = 0;
for (int i = n - 1; i >= 0; i--)
{
if (a[i] % 2 == 1)
{
// s is the count of subarrays starting from
// index i+1 whose sum was even
/*if a[i] is odd then all subarrays starting
from index i+1 which was odd becomeseven
when a[i] gets added to it.*/
s = n - i - 1 - s;
}
else
{
/*if a[i] is even then all subarrays
starting from index i+1 which was even remainseven
and one extra a[i] even subarray gets added to it.*/
s = s + 1;
}
res = res + s;
}
return res;
}
// Driver Code
static public void Main ()
{
int[] arr = { 1, 2, 2, 3, 4, 1 };
int n = arr.Length;
Console.WriteLine("The Number of Subarrays"
+ " with even sum is "
+ countEvenSum(arr, n));
}
}
// This code is contributed by avanitrachhadiya2155
Javascript
<script>
// Javascript program to count
// number of sub-arrays
// with even sum using an
// efficient algorithm
// Time Complexity - O(N)
// Space Complexity - O(1)
function countEvenSum(a, n)
{
// result may be large enough not to
// fit in int;
let res = 0;
// to keep track of subarrays with even
// sum starting from index i
let s = 0;
for (let i = n - 1; i >= 0; i--)
{
if (a[i] % 2 == 1)
{
// s is the count of subarrays starting from
// index i+1 whose sum was even
/*if a[i] is odd then all subarrays starting
from index i+1 which was odd becomeseven
when a[i] gets added to it.*/
s = n - i - 1 - s;
}
else
{
/*if a[i] is even then all subarrays
starting from index i+1 which was even remainseven
and one extra a[i] even subarray gets added to it.*/
s = s + 1;
}
res = res + s;
}
return res;
}
let arr = [ 1, 2, 2, 3, 4, 1 ];
let n = arr.length;
document.write("The Number of Subarrays" +
" with even sum is " + countEvenSum(arr, n));
</script>
Producción
The Number of Subarrays with even sum is 9
Complejidad de tiempo: O(n)
Espacio Auxiliar: O(1)
Este artículo es una contribución de Rachit Belwariar . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo 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