Dado un arreglo de n elementos y un entero m, necesitamos escribir un programa para encontrar el número de subarreglos contiguos en el arreglo que contiene exactamente m números impares.
Ejemplos:
Entrada: arr = {2, 5, 6, 9}, m = 2
Salida: 2
Explicación:
los subarreglos son [2, 5, 6, 9]
y [5, 6, 9]Entrada: arr = {2, 2, 5, 6, 9, 2, 11}, m = 2
Salida: 8
Explicación:
los subarreglos son [2, 2, 5, 6, 9],
[2, 5, 6, 9 ], [5, 6, 9], [2, 2, 5, 6, 9, 2],
[2, 5, 6, 9, 2], [5, 6, 9, 2], [6, 9 , 2, 11]
y [9, 2, 11]
Enfoque ingenuo : el enfoque ingenuo es generar todos los subarreglos posibles y verificar simultáneamente los subarreglos con números m impares.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to count the
// Number of subarrays with
// m odd numbers
#include <bits/stdc++.h>
using namespace std;
// function that returns
// the count of subarrays
// with m odd numbers
int countSubarrays(int a[], int n, int m)
{
int count = 0;
// traverse for all
// possible subarrays
for (int i = 0; i < n; i++)
{
int odd = 0;
for (int j = i; j < n; j++)
{
if (a[j] % 2)
odd++;
// if count of odd numbers in
// subarray is m
if (odd == m)
count++;
}
}
return count;
}
// Driver Code
int main()
{
int a[] = { 2, 2, 5, 6, 9, 2, 11 };
int n = sizeof(a) / sizeof(a[0]);
int m = 2;
cout << countSubarrays(a, n, m);
return 0;
}
Java
// Java program to count the number of
// subarrays with m odd numbers
import java.util.*;
class GFG {
// function that returns the count of
// subarrays with m odd numbers
static int countSubarrays(int a[], int n, int m)
{
int count = 0;
// traverse for all possible
// subarrays
for (int i = 0; i < n; i++)
{
int odd = 0;
for (int j = i; j < n; j++)
{
if (a[j] % 2 != 0)
odd++;
// if count of odd numbers
// in subarray is m
if (odd == m)
count++;
}
}
return count;
}
// Driver code
public static void main(String[] args)
{
int a[] = { 2, 2, 5, 6, 9, 2, 11 };
int n = a.length;
int m = 2;
System.out.println(countSubarrays(a, n, m));
}
}
// This code is contributed by akash1295.
Python3
# Python3 program to count the # Number of subarrays with # m odd numbers # function that returns the count # of subarrays with m odd numbers def countSubarrays(a, n, m): count = 0 # traverse for all # possible subarrays for i in range(n): odd = 0 for j in range(i, n): if (a[j] % 2): odd += 1 # if count of odd numbers # in subarray is m if (odd == m): count += 1 return count # Driver Code a = [2, 2, 5, 6, 9, 2, 11] n = len(a) m = 2 print(countSubarrays(a, n, m)) # This code is contributed by mits
C#
// C# program to count the number of
// subarrays with m odd numbers
using System;
class GFG {
// function that returns the count of
// subarrays with m odd numbers
static int countSubarrays(int[] a, int n, int m)
{
int count = 0;
// traverse for all possible
// subarrays
for (int i = 0; i < n; i++)
{
int odd = 0;
for (int j = i; j < n; j++)
{
if (a[j] % 2 == 0)
odd++;
// if count of odd numbers
// in subarray is m
if (odd == m)
count++;
}
}
return count;
}
// Driver code
public static void Main()
{
int[] a = { 2, 2, 5, 6, 9, 2, 11 };
int n = a.Length;
int m = 2;
Console.WriteLine(countSubarrays(a, n, m));
}
}
// This code is contributed by anuj_67.
PHP
<?php
// PHP program to count the
// Number of subarrays with
// m odd numbers
// function that returns the count
// of subarrays with m odd numbers
function countSubarrays( $a, $n, $m)
{
$count = 0;
// traverse for all
// possible subarrays
for ( $i = 0; $i < $n; $i++)
{
$odd = 0;
for ( $j = $i; $j < $n; $j++)
{
if ($a[$j] % 2)
$odd++;
// if count of odd numbers in
// subarray is m
if ($odd == $m)
$count++;
}
}
return $count;
}
// Driver Code
$a = array( 2, 2, 5, 6, 9, 2, 11 );
$n = count($a);
$m = 2;
echo countSubarrays($a, $n, $m);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// javascript program to count the number of
// subarrays with m odd numbers
// function that returns the count of
// subarrays with m odd numbers
function countSubarrays(a, n, m)
{
var count = 0;
// traverse for all possible
// subarrays
for (var i = 0; i < n; i++)
{
var odd = 0;
for (var j = i; j < n; j++)
{
if (a[j] % 2 == 0)
odd++;
// if count of odd numbers
// in subarray is m
if (odd == m)
count++;
}
}
return count;
}
// Driver code
var a = [ 2, 2, 5, 6, 9, 2, 11 ];
var n = a.length;
var m = 2;
document.write(countSubarrays(a, n, m));
// This code is contributed by bunnyram19.
</script>
Producción :
8
Complejidad temporal: O(n 2 )
Espacio Auxiliar : O(1)
Enfoque eficiente: un enfoque eficiente es calcular la array de prefijo [] mientras se atraviesa. Prefix[i] almacena el número de prefijos que tienen números impares ‘i’ . Aumentamos el conteo de números impares si el elemento de la array es impar. Cuando el conteo de números impares exceda o sea igual a m, agregue el número de prefijos que tiene números «(impar-m)» a la respuesta. En cada paso impar>=m, calculamos el número de subarreglos formados hasta un índice particular con la ayuda de la array de prefijos. prefix[odd-m] nos proporciona la cantidad de prefijos que tienen números impares «odd-m», que se agregan al conteo para obtener la cantidad de subarreglos hasta el índice.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to count the Number
// of subarrays with m odd numbers
// O(N) approach
#include <bits/stdc++.h>
using namespace std;
// function that returns the count
// of subarrays with m odd numbers
int countSubarrays(int a[], int n, int m)
{
int count = 0;
int prefix[n + 1] = { 0 };
int odd = 0;
// traverse in the array
for (int i = 0; i < n; i++)
{
prefix[odd]++;
// if array element is odd
if (a[i] & 1)
odd++;
// when number of odd elements>=M
if (odd >= m)
count += prefix[odd - m];
}
return count;
}
// Driver Code
int main()
{
int a[] = { 2, 2, 5, 6, 9, 2, 11 };
int n = sizeof(a) / sizeof(a[0]);
int m = 2;
cout << countSubarrays(a, n, m);
return 0;
}
Java
// Java program to count the
// number of subarrays with
// m odd numbers
import java.util.*;
class GFG {
// function that returns the count of
// subarrays with m odd numbers
public static int countSubarrays(int a[], int n, int m)
{
int count = 0;
int prefix[] = new int[n + 1];
int odd = 0;
// Traverse in the array
for (int i = 0; i < n; i++)
{
prefix[odd]++;
// If array element is odd
if ((a[i] & 1) == 1)
odd++;
// When number of odd
// elements >= M
if (odd >= m)
count += prefix[odd - m];
}
return count;
}
// Driver code
public static void main(String[] args)
{
int a[] = { 2, 2, 5, 6, 9, 2, 11 };
int n = a.length;
int m = 2;
// Function call
System.out.println(countSubarrays(a, n, m));
}
}
// This code is contributed by akash1295.
Python3
# Python3 program to count the Number # of subarrays with m odd numbers # O(N) approach # function that returns the count # of subarrays with m odd numbers def countSubarrays(a, n, m): count = 0 prefix = [0] * (n+1) odd = 0 # traverse in the array for i in range(n): prefix[odd] += 1 # if array element is odd if (a[i] & 1): odd += 1 # when number of odd elements>=M if (odd >= m): count += prefix[odd - m] return count # Driver Code a = [2, 2, 5, 6, 9, 2, 11] n = len(a) m = 2 print(countSubarrays(a, n, m)) # This code is contributed 29Ajaykumar
C#
// C# program to count the number of
// subarrays with m odd numbers
using System;
class GFG {
// function that returns the count of
// subarrays with m odd numbers
public static int countSubarrays(int[] a, int n, int m)
{
int count = 0;
int[] prefix = new int[n + 1];
int odd = 0;
// traverse in the array
for (int i = 0; i < n; i++)
{
prefix[odd]++;
// if array element is odd
if ((a[i] & 1) == 1)
odd++;
// when number of odd
// elements >= M
if (odd >= m)
count += prefix[odd - m];
}
return count;
}
// Driver code
public static void Main()
{
int[] a = { 2, 2, 5, 6, 9, 2, 11 };
int n = a.Length;
int m = 2;
Console.WriteLine(countSubarrays(a, n, m));
}
}
// This code is contributed by anuj_67.
PHP
<?php
// PHP program to count the Number
// of subarrays with m odd numbers
// O(N) approach
// function that returns the count
// of subarrays with m odd numbers
function countSubarrays(&$a, $n, $m)
{
$count = 0;
$prefix[$n+1] = array();
$odd = 0;
// traverse in the array
for ($i = 0; $i < $n; $i++)
{
$prefix[$odd]++;
// if array element is odd
if ($a[$i] & 1)
$odd++;
// when number of odd elements>=M
if ($odd >= $m)
$count += $prefix[$odd - $m];
}
return $count;
}
// Driver Code
$a = array(2, 2, 5, 6, 9, 2, 11 );
$n = sizeof($a);
$m = 2;
echo countSubarrays($a, $n, $m);
// This code is contributed
// by Shivi_Aggarwal
?>
Javascript
<script>
// Javascript program to count the number of
// subarrays with m odd numbers
// function that returns the count of
// subarrays with m odd numbers
function countSubarrays(a, n, m)
{
let count = 0;
let prefix = new Array(n + 1);
prefix.fill(0);
let odd = 0;
// traverse in the array
for (let i = 0; i < n; i++)
{
prefix[odd]++;
// if array element is odd
if ((a[i] & 1) == 1)
odd++;
// when number of odd
// elements >= M
if (odd >= m)
count += prefix[odd - m];
}
return count;
}
let a = [ 2, 2, 5, 6, 9, 2, 11 ];
let n = a.length;
let m = 2;
document.write(countSubarrays(a, n, m));
// This code is contributed by divyeshrabadiya07.
</script>
Producción :
8
Complejidad de tiempo: O(n)
Espacio Auxiliar: O(n)