Dada una array, encuentre el número de subarreglos cuya suma es impar.
Ejemplos:
Input : arr[] = {5, 4, 4, 5, 1, 3}
Output : 12
There are possible subarrays with odd
sum. The subarrays are
1) {5} Sum = 5 (At index 0)
2) {5, 4} Sum = 9
3) {5, 4, 4} Sum = 13
4) {5, 4, 4, 5, 1} Sum = 19
5) {4, 4, 5} Sum = 13
6) {4, 4, 5, 1, 3} Sum = 17
7) {4, 5} Sum = 9
8) {4, 5, 1, 3} Sum = 13
9) {5} Sum = 5 (At index 3)
10) {5, 1, 3} Sum = 9
11) {1} Sum = 1
12) {3} Sum = 3
Método O(n 2 ) tiempo y O(1) espacio [Fuerza bruta]
Simplemente podemos generar todos los sub-arreglos posibles y encontrar si la suma de todos los elementos en ellos es impar o no. Si es impar, contaremos ese subarreglo; de lo contrario, lo descartaremos.
C++
// C++ code to find count of sub-arrays with odd sum
#include <bits/stdc++.h>
using namespace std;
int countOddSum(int ar[], int n)
{
int result = 0;
// Find sum of all subarrays and increment result if sum
// is odd
for (int i = 0; i <= n - 1; i++) {
int val = 0;
for (int j = i; j <= n - 1; j++) {
val = val + ar[j];
if (val % 2 != 0)
result++;
}
}
return (result);
}
// Driver code
int main()
{
int arr[] = { 5, 4, 4, 5, 1, 3 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "The Number of Subarrays with odd sum is "
<< countOddSum(arr, n);
return (0);
}
// This code is contributed by Sania Kumari Gupta
C
// C++ code to find count of sub-arrays with odd sum
#include <stdio.h>
int countOddSum(int ar[], int n)
{
int result = 0;
// Find sum of all subarrays and increment result if sum
// is odd
for (int i = 0; i <= n - 1; i++) {
int val = 0;
for (int j = i; j <= n - 1; j++) {
val = val + ar[j];
if (val % 2 != 0)
result++;
}
}
return (result);
}
// Driver code
int main()
{
int arr[] = { 5, 4, 4, 5, 1, 3 };
int n = sizeof(arr) / sizeof(arr[0]);
printf("The Number of Subarrays with odd sum is %d",
countOddSum(arr, n));
return (0);
}
// This code is contributed by Sania Kumari Gupta
Java
// Java code to find count of sub-arrays with odd sum
import java.io.*;
class GFG {
static int countOddSum(int ar[], int n)
{
int result = 0;
// Find sum of all subarrays and increment result if
// sum is odd
for (int i = 0; i <= n - 1; i++) {
int val = 0;
for (int j = i; j <= n - 1; j++) {
val = val + ar[j];
if (val % 2 != 0)
result++;
}
}
return (result);
}
// Driver code
public static void main(String[] args)
{
int ar[] = { 5, 4, 4, 5, 1, 3 };
int n = ar.length;
System.out.print(
"The Number of Subarrays with odd sum is ");
System.out.println(countOddSum(ar, n));
}
}
// This code is contributed by Sania Kumari Gupta
Python3
# Python 3 code to find count
# of sub-arrays with odd sum
def countOddSum(ar, n):
result = 0
# Find sum of all subarrays and
# increment result if sum is odd
for i in range(n):
val = 0
for j in range(i, n ):
val = val + ar[j]
if (val % 2 != 0):
result +=1
return (result)
# Driver code
ar = [ 5, 4, 4, 5, 1, 3 ]
print("The Number of Subarrays" ,
"with odd", end = "")
print(" sum is "+ str(countOddSum(ar, 6)))
# This code is contributed
# by ChitraNayal
C#
// C# code to find count
// of sub-arrays with odd sum
using System;
class GFG
{
static int countOddSum(int []ar,
int n)
{
int result = 0;
// Find sum of all subarrays
// and increment result if
// sum is odd
for (int i = 0;
i <= n - 1; i++)
{
int val = 0;
for (int j = i;
j <= n - 1; j++)
{
val = val + ar[j];
if (val % 2 != 0)
result++;
}
}
return (result);
}
// Driver code
public static void Main()
{
int []ar = {5, 4, 4, 5, 1, 3};
int n = ar.Length;
Console.Write("The Number of Subarrays" +
" with odd sum is ");
Console.WriteLine(countOddSum(ar, n));
}
}
// This code is contributed
// by chandan_jnu.
PHP
<?php
// PHP code to find count
// of sub-arrays with odd sum
function countOddSum(&$ar, $n)
{
$result = 0;
// Find sum of all subarrays and
// increment result if sum is odd
for ($i = 0; $i <= $n - 1; $i++)
{
$val = 0;
for ($j = $i;
$j <= $n - 1; $j++)
{
$val = $val + $ar[$j];
if ($val % 2 != 0)
$result++;
}
}
return ($result);
}
// Driver code
$ar = array(5, 4, 4, 5, 1, 3);
$n = sizeof($ar);
echo "The Number of Subarrays with odd ";
echo "sum is ".countOddSum($ar, $n);
// This code is contributed
// by ChitraNayal
?>
Javascript
<script>
// Javascript code to find count of
// sub-arrays with odd sum
function countOddSum(ar, n)
{
let result = 0;
// Find sum of all subarrays
// and increment result if
// sum is odd
for(let i = 0; i <= n - 1; i++)
{
let val = 0;
for(let j = i; j <= n - 1; j++)
{
val = val + ar[j];
if (val % 2 != 0)
result++;
}
}
return (result);
}
// Driver code
let ar = [ 5, 4, 4, 5, 1, 3 ];
let n = ar.length;
document.write("The Number of Subarrays" +
" with odd sum is ");
document.write(countOddSum(ar, n));
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
The Number of Subarrays with odd sum is 12
Complejidad temporal: O(n 2 )
Espacio auxiliar: O(1)
O(n) Tiempo y O(1) Método espacial [Eficiente]
Si calculamos la array de suma acumulada en temp[] de nuestra array de entrada, entonces podemos ver que la sub-array comienza desde i y termina en j, tiene una suma par si temp[] si (temp[j] – temp[i]) % 2 = 0. Entonces, en lugar de construir una array de suma acumulativa, construimos una array de suma acumulativa módulo 2. Luego, el cálculo de pares impares dará el resultado requerido, es decir, temp[0]*temp[1].
C++
// C++ program to find count of sub-arrays
// with odd sum
#include <bits/stdc++.h>
using namespace std;
int countOddSum(int ar[], 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 odd 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, val = 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
val = ((val + ar[i]) % 2 + 2) % 2;
// Increment even/odd count
temp[val]++;
}
// An odd can be formed by even-odd pair
result = (temp[0] * temp[1]);
return (result);
}
// Driver code
int main()
{
int ar[] = { 5, 4, 4, 5, 1, 3 };
int n = sizeof(ar) / sizeof(ar[0]);
cout << "The Number of Subarrays with odd sum is "
<< countOddSum(ar, n);
return (0);
}
// This code is contributed by Sania Kumari Gupta
C
// C++ program to find count of sub-arrays
// with odd sum
#include <stdio.h>
int countOddSum(int ar[], 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 odd 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, val = 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
val = ((val + ar[i]) % 2 + 2) % 2;
// Increment even/odd count
temp[val]++;
}
// An odd can be formed by even-odd pair
result = (temp[0] * temp[1]);
return (result);
}
// Driver code
int main()
{
int ar[] = { 5, 4, 4, 5, 1, 3 };
int n = sizeof(ar) / sizeof(ar[0]);
printf("The Number of Subarrays with odd sum is %d",
countOddSum(ar, n));
return (0);
}
// This code is contributed by Sania Kumari Gupta
Java
// Java code to find count of sub-arrays
// with odd sum
import java.io.*;
class GFG {
static int countOddSum(int ar[], 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 odd 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, val = 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
val = ((val + ar[i]) % 2 + 2) % 2;
// Increment even/odd count
temp[val]++;
}
// An odd can be formed by an even-odd pair
result = temp[0] * temp[1];
return (result);
}
// Driver code
public static void main(String[] args)
{
int ar[] = { 5, 4, 4, 5, 1, 3 };
int n = ar.length;
System.out.println(
"The Number of Subarrays with odd sum is "
+ countOddSum(ar, n));
}
}
// This code is contributed by Sania Kumari Gupta
Python3
# Python 3 program to
# find count of sub-arrays
# with odd sum
def countOddSum(ar, 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 is a single odd
# 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
val = 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
val = ((val + ar[i]) % 2 + 2) % 2
# Increment even/odd count
temp[val] += 1
# An odd can be formed
# by even-odd pair
result = (temp[0] * temp[1])
return (result)
# Driver code
ar = [ 5, 4, 4, 5, 1, 3 ]
print("The Number of Subarrays"
" with odd sum is "+
str(countOddSum(ar, 6)))
# This code is contributed
# by ChitraNayal
C#
// C# code to find count of
// sub-arrays with odd sum
using System;
class GFG
{
static int countOddSum(int[] ar,
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 odd
// 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, val = 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
val = ((val + ar[i]) % 2 + 2) % 2;
// Increment even/odd count
temp[val]++;
}
// An odd can be formed
// by an even-odd pair
result = temp[0] * temp[1];
return (result);
}
// Driver code
public static void Main()
{
int[] ar = { 5, 4, 4, 5, 1, 3 };
int n = ar.Length;
Console.Write("The Number of Subarrays" +
" with odd sum is " +
countOddSum(ar, n));
}
}
// This code is contributed
// by ChitraNayal
PHP
<?php
// PHP program to find count
// of sub-arrays with odd sum
function countOddSum($ar, $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 is a single odd
// 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;
$val = 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
$val = (($val + $ar[$i]) %
2 + 2) % 2;
// Increment even/odd count
$temp[$val]++;
}
// An odd can be formed
// by even-odd pair
$result = ($temp[0] * $temp[1]);
return ($result);
}
// Driver code
$ar = array(5, 4, 4, 5, 1, 3);
$n = sizeof($ar);
echo "The Number of Subarrays with odd".
" sum is ".countOddSum($ar, $n);
// This code is contributed
// by ChitraNayal
?>
Javascript
<script>
// Javascript code to find count of
// sub-arrays with odd sum
function countOddSum(ar, 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 odd
// 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, val = 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
val = ((val + ar[i]) % 2 + 2) % 2;
// Increment even/odd count
temp[val]++;
}
// An odd can be formed
// by an even-odd pair
result = temp[0] * temp[1];
return (result);
}
// Driver code
let ar = [ 5, 4, 4, 5, 1, 3 ];
let n = ar.length;
document.write("The Number of Subarrays" +
" with odd sum is " +
countOddSum(ar, n));
// This code is contributed by rameshtravel07
</script>
Producción:
The Number of Subarrays with odd sum is 12
Complejidad de tiempo: O(n)
Espacio auxiliar: O(1)
Otro enfoque eficiente es encontrar primero el número de subarreglos que comienzan en el índice 0 y tienen una suma impar. Luego recorra la array y actualice la cantidad de subarreglos que comienzan en el índice i y tienen una suma impar.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find number of subarrays with odd sum
#include <bits/stdc++.h>
using namespace std;
// Function to find number of subarrays with odd sum
int countOddSum(int a[], int n)
{
// 'odd' stores number of odd numbers upto ith index
// 'c_odd' stores number of odd sum subarrays starting
// at ith index
//'Result' stores the number of odd sum subarrays
int odd = 0, c_odd = 0, result = 0;
// First find number of odd sum subarrays starting at
// 0th index
for (int i = 0; i < n; i++) {
if (a[i] & 1)
odd = !odd;
if (odd)
c_odd++;
}
// Find number of odd sum subarrays starting at ith
// index add to result
for (int i = 0; i < n; i++) {
result += c_odd;
if (a[i] & 1)
c_odd = (n - i - c_odd);
}
return result;
}
// Driver code
int main()
{
int ar[] = { 5, 4, 4, 5, 1, 3 };
int n = sizeof(ar) / sizeof(ar[0]);
cout << "The Number of Subarrays with odd sum is "
<< countOddSum(ar, n);
return (0);
}
// This code is contributed by Sania Kumari Gupta
C
// C++ program to find number of subarrays with odd sum
#include <stdio.h>
// Function to find number of subarrays with odd sum
int countOddSum(int a[], int n)
{
// 'odd' stores number of odd numbers upto ith index
// 'c_odd' stores number of odd sum subarrays starting
// at ith index
//'Result' stores the number of odd sum subarrays
int odd = 0, c_odd = 0, result = 0;
// First find number of odd sum subarrays starting at
// 0th index
for (int i = 0; i < n; i++) {
if (a[i] & 1)
odd = !odd;
if (odd)
c_odd++;
}
// Find number of odd sum subarrays starting at ith
// index add to result
for (int i = 0; i < n; i++) {
result += c_odd;
if (a[i] & 1)
c_odd = (n - i - c_odd);
}
return result;
}
// Driver code
int main()
{
int ar[] = { 5, 4, 4, 5, 1, 3 };
int n = sizeof(ar) / sizeof(ar[0]);
printf("The Number of Subarrays with odd sum is %d",
countOddSum(ar, n));
return (0);
}
// This code is contributed by Sania Kumari Gupta
Java
// Java program to find number of subarrays
// with odd sum
import java.util.*;
class GFG {
// Function to find number of subarrays with odd sum
static int countOddSum(int a[], int n)
{
// 'odd' stores number of odd numbers upto ith index
// 'c_odd' stores number of odd sum subarrays starting at ith index
//'Result' stores the number of odd sum subarrays
int c_odd = 0, result = 0;
boolean odd = false;
// First find number of odd sum subarrays starting
// at 0th index
for (int i = 0; i < n; i++) {
if (a[i] % 2 == 1)
odd = !odd;
if (odd)
c_odd++;
}
// Find number of odd sum subarrays starting at ith
// index add to result
for (int i = 0; i < n; i++) {
result += c_odd;
if (a[i] % 2 == 1)
c_odd = (n - i - c_odd);
}
return result;
}
// Driver code
public static void main(String[] args)
{
int ar[] = { 5, 4, 4, 5, 1, 3 };
int n = ar.length;
System.out.print(
"The Number of Subarrays with odd sum is "
+ countOddSum(ar, n));
}
}
// This code is contributed by Sania Kumari Gupta
Python3
# Python3 program to find
# number of subarrays with
# odd sum
# Function to find number
# of subarrays with odd sum
def countOddSum(a, n):
# 'odd' stores number of
# odd numbers upto ith index
# 'c_odd' stores number of
# odd sum subarrays starting
# at ith index
# 'Result' stores the number
# of odd sum subarrays
c_odd = 0;
result = 0;
odd = False;
# First find number of odd
# sum subarrays starting at
# 0th index
for i in range(n):
if (a[i] % 2 == 1):
if(odd == True):
odd = False;
else:
odd = True;
if (odd):
c_odd += 1;
# Find number of odd sum
# subarrays starting at ith
# index add to result
for i in range(n):
result += c_odd;
if (a[i] % 2 == 1):
c_odd = (n - i - c_odd);
return result;
# Driver code
if __name__ == '__main__':
ar = [5, 4, 4, 5, 1, 3];
n = len(ar);
print("The Number of Subarrays" +
"with odd sum is " ,
countOddSum(ar, n));
# This code is contributed by shikhasingrajput
C#
// C# program to find number of subarrays
// with odd sum
using System;
public class GFG{
// Function to find number of
// subarrays with odd sum
static int countOddSum(int []a, int n)
{
// 'odd' stores number of odd numbers
// upto ith index
// 'c_odd' stores number of odd sum
// subarrays starting at ith index
// 'Result' stores the number of
// odd sum subarrays
int c_odd = 0, result = 0;
bool odd = false;
// First find number of odd sum
// subarrays starting at 0th index
for(int i = 0; i < n; i++)
{
if (a[i] % 2 == 1)
{
odd = !odd;
}
if (odd)
{
c_odd++;
}
}
// Find number of odd sum subarrays
// starting at ith index add to result
for(int i = 0; i < n; i++)
{
result += c_odd;
if (a[i] % 2 == 1)
{
c_odd = (n - i - c_odd);
}
}
return result;
}
// Driver code
public static void Main(String[] args)
{
int []ar = { 5, 4, 4, 5, 1, 3 };
int n = ar.Length;
Console.Write("The Number of Subarrays " +
"with odd sum is " +
countOddSum(ar, n));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript program to find number
// of subarrays with odd sum
// Function to find number of
// subarrays with odd sum
function countOddSum(a, n)
{
// 'odd' stores number of odd numbers
// upto ith index
// 'c_odd' stores number of odd sum
// subarrays starting at ith index
// 'Result' stores the number of
// odd sum subarrays
let c_odd = 0, result = 0;
let odd = false;
// First find number of odd sum
// subarrays starting at 0th index
for(let i = 0; i < n; i++)
{
if (a[i] % 2 == 1)
{
odd = !odd;
}
if (odd)
{
c_odd++;
}
}
// Find number of odd sum subarrays
// starting at ith index add to result
for(let i = 0; i < n; i++)
{
result += c_odd;
if (a[i] % 2 == 1)
{
c_odd = (n - i - c_odd);
}
}
return result;
}
let ar = [ 5, 4, 4, 5, 1, 3 ];
let n = ar.length;
document.write("The Number of Subarrays " +
"with odd sum is " +
countOddSum(ar, n));
</script>
Producción:
The Number of Subarrays with odd sum is 12
Complejidad de tiempo: O(n)
Espacio Auxiliar: O(1)