Dada una array de enteros arr[] de tamaño N , la tarea es contar el número de sub-arrays que tienen un producto impar.
Ejemplos:
Entrada: array[] = {5, 1, 2, 3, 4}
Salida: 4
Explicación: Las sub-arrays con producto impar son-
{5}, {1}, {3}, {5, 1}. Por lo tanto, la cuenta es 4.
Entrada: arr[] = {12, 15, 7, 3, 25, 6, 2, 1, 1, 7}
Salida: 16
Enfoque ingenuo: una solución simple es calcular el producto de cada subarreglo y verificar si es impar o no y calcular el conteo en consecuencia.
Complejidad de tiempo: O(N 2 )
Enfoque eficiente: Un producto impar es posible solo por el producto de números impares. Por lo tanto, por cada K números impares continuos en la array, el recuento de sub-arrays con el producto impar aumenta en K*(K+1)/2 . Una forma de contar números impares continuos es calcular la diferencia entre los índices de cada dos números pares consecutivos y restarla por 1 . Para el cálculo, -1 y N se consideran índices de números pares.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the count of
// sub-arrays with odd product
#include <bits/stdc++.h>
using namespace std;
// Function that returns the count of
// sub-arrays with odd product
int countSubArrayWithOddProduct(int* A, int N)
{
// Initialize the count variable
int count = 0;
// Initialize variable to store the
// last index with even number
int last = -1;
// Initialize variable to store
// count of continuous odd numbers
int K = 0;
// Loop through the array
for (int i = 0; i < N; i++) {
// Check if the number
// is even or not
if (A[i] % 2 == 0) {
// Calculate count of continuous
// odd numbers
K = (i - last - 1);
// Increase the count of sub-arrays
// with odd product
count += (K * (K + 1) / 2);
// Store the index of last
// even number
last = i;
}
}
// N considered as index of
// even number
K = (N - last - 1);
count += (K * (K + 1) / 2);
return count;
}
// Driver Code
int main()
{
int arr[] = { 12, 15, 7, 3, 25,
6, 2, 1, 1, 7 };
int n = sizeof(arr) / sizeof(arr[0]);
// Function call
cout << countSubArrayWithOddProduct(arr, n);
return 0;
}
Java
// Java program to find the count of
// sub-arrays with odd product
class GFG {
// Function that returns the count of
// sub-arrays with odd product
static int countSubArrayWithOddProduct(int A[],
int N)
{
// Initialize the count variable
int count = 0;
// Initialize variable to store the
// last index with even number
int last = -1;
// Initialize variable to store
// count of continuous odd numbers
int K = 0;
// Loop through the array
for(int i = 0; i < N; i++)
{
// Check if the number
// is even or not
if (A[i] % 2 == 0)
{
// Calculate count of continuous
// odd numbers
K = (i - last - 1);
// Increase the count of sub-arrays
// with odd product
count += (K * (K + 1) / 2);
// Store the index of last
// even number
last = i;
}
}
// N considered as index of
// even number
K = (N - last - 1);
count += (K * (K + 1) / 2);
return count;
}
// Driver Code
public static void main(String args[])
{
int arr[] = { 12, 15, 7, 3, 25, 6, 2, 1, 1, 7 };
int n = arr.length;
// Function call
System.out.println(countSubArrayWithOddProduct(arr, n));
}
}
// This code is contributed by rutvik_56
Python3
# Python3 program to find the count of # sub-arrays with odd product # Function that returns the count of # sub-arrays with odd product def countSubArrayWithOddProduct(A, N): # Initialize the count variable count = 0 # Initialize variable to store the # last index with even number last = -1 # Initialize variable to store # count of continuous odd numbers K = 0 # Loop through the array for i in range(N): # Check if the number # is even or not if (A[i] % 2 == 0): # Calculate count of continuous # odd numbers K = (i - last - 1) # Increase the count of sub-arrays # with odd product count += (K * (K + 1) / 2) # Store the index of last # even number last = i # N considered as index of # even number K = (N - last - 1) count += (K * (K + 1) / 2) return count # Driver Code if __name__ == '__main__': arr = [ 12, 15, 7, 3, 25, 6, 2, 1, 1, 7 ] n = len(arr) # Function call print(int(countSubArrayWithOddProduct(arr, n))) # This code is contributed by Bhupendra_Singh
C#
// C# program to find the count of
// sub-arrays with odd product
using System;
class GFG{
// Function that returns the count of
// sub-arrays with odd product
static int countSubArrayWithOddProduct(int[] A,
int N)
{
// Initialize the count variable
int count = 0;
// Initialize variable to store the
// last index with even number
int last = -1;
// Initialize variable to store
// count of continuous odd numbers
int K = 0;
// Loop through the array
for(int i = 0; i < N; i++)
{
// Check if the number
// is even or not
if (A[i] % 2 == 0)
{
// Calculate count of continuous
// odd numbers
K = (i - last - 1);
// Increase the count of sub-arrays
// with odd product
count += (K * (K + 1) / 2);
// Store the index of last
// even number
last = i;
}
}
// N considered as index of
// even number
K = (N - last - 1);
count += (K * (K + 1) / 2);
return count;
}
// Driver code
static void Main()
{
int[] arr = { 12, 15, 7, 3, 25,
6, 2, 1, 1, 7 };
int n = arr.Length;
// Function call
Console.WriteLine(countSubArrayWithOddProduct(arr, n));
}
}
// This code is contributed by divyeshrabadiya07
Javascript
<script>
// Javascript program to find the count of
// sub-arrays with odd product
// Function that returns the count of
// sub-arrays with odd product
function countSubArrayWithOddProduct(A, N)
{
// Initialize the count variable
var count = 0;
// Initialize variable to store the
// last index with even number
var last = -1;
// Initialize variable to store
// count of continuous odd numbers
var K = 0;
// Loop through the array
for (var i = 0; i < N; i++)
{
// Check if the number
// is even or not
if (A[i] % 2 == 0)
{
// Calculate count of continuous
// odd numbers
K = (i - last - 1);
// Increase the count of sub-arrays
// with odd product
count += (K * (K + 1) / 2);
// Store the index of last
// even number
last = i;
}
}
// N considered as index of
// even number
K = (N - last - 1);
count += (K * (K + 1) / 2);
return count;
}
// Driver Code
var arr = [ 12, 15, 7, 3, 25,
6, 2, 1, 1, 7 ];
var n = arr.length;
// Function call
document.write( countSubArrayWithOddProduct(arr, n));
// This code is contributed by rrrtnx.
</script>
Producción:
16
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por rupesh_rao y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA