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>
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>
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>
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