Dada una array arr[] de tamaño N , la tarea es encontrar el número de subsecuencias no vacías de la array dada de modo que no haya dos elementos adyacentes de la subsecuencia que tengan la misma paridad .
Ejemplos:
Entrada: arr[] = [5, 6, 9, 7]
Salida: 9
Explicación:
Todas esas subsecuencias de la array dada serán {5}, {6}, {9}, {7}, {5, 6}, {6, 7}, {6, 9}, {5, 6, 9}, {5, 6, 7} .
Entrada: arr[] = [2, 3, 4, 8]
Salida: 9
Enfoque ingenuo: genere todas las subsecuencias que no estén vacías y seleccione las que tengan números pares-impares o pares -impares alternos y cuente todas esas subsecuencias para obtener la respuesta.
Complejidad de tiempo: O(2 N )
Enfoque eficiente:
El enfoque anterior se puede optimizar mediante la programación dinámica . Siga los pasos a continuación para resolver el problema:
- Considere una array dp[] de dimensiones (N+1)*(2) .
- dp[i][0] almacena el conteo de subsecuencias hasta el i -ésimo índice que termina con un elemento par .
- dp[i][1] almacena el recuento de subsecuencias hasta el i -ésimo índice que termina con un elemento impar .
- Por lo tanto, para cada i -ésimo elemento , verifique si el elemento es par o impar y proceda incluyendo y excluyendo el i -ésimo elemento .
- Por lo tanto, la relación de recurrencia si el i -ésimo elemento es impar:
dp[i][1] = dp[i – 1][0] (Incluyendo el i -ésimo elemento considerando todas las subsecuencias que terminan con el elemento par hasta (i – 1) el índice ) + 1 + dp[i – 1][ 1] (Excluyendo el i -ésimo elemento)
- De manera similar, si el i -ésimo elemento es par:
dp[i][0] = dp[i – 1][1] (Incluyendo el i -ésimo elemento considerando todas las subsecuencias que terminan con el elemento impar hasta (i – 1) el índice ) + 1 + dp[i – 1][ 0] (Excluyendo el i -ésimo elemento)
- Finalmente, la suma de dp[n][0], que contiene todas las subsecuencias que terminan en un elemento par, y dp[n][1], que contiene todas las subsecuencias que terminan en un elemento impar, es la respuesta requerida.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to implement the
// above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find required subsequences
int validsubsequences(int arr[], int n)
{
// dp[i][0]: Stores the number of
// subsequences till i-th index
// ending with even element
// dp[i][1]: Stores the number of
// subsequences till i-th index
// ending with odd element
long long int dp[n + 1][2];
// Initialise the dp[][] with 0.
for (int i = 0; i < n + 1; i++) {
dp[i][0] = 0;
dp[i][1] = 0;
}
for (int i = 1; i <= n; i++) {
// If odd element is
// encountered
if (arr[i - 1] % 2) {
// Considering i-th element
// will be present in
// the subsequence
dp[i][1] += 1;
// Appending i-th element to all
// non-empty subsequences
// ending with even element
// till (i-1)th indexes
dp[i][1] += dp[i - 1][0];
// Considering ith element will
// not be present in
// the subsequence
dp[i][1] += dp[i - 1][1];
dp[i][0] += dp[i - 1][0];
}
else {
// Considering i-th element
// will be present in
// the subsequence
dp[i][0] += 1;
// Appending i-th element to all
// non-empty subsequences
// ending with odd element
// till (i-1)th indexes
dp[i][0] += dp[i - 1][1];
// Considering ith element will
// not be present in
// the subsequence
dp[i][0] += dp[i - 1][0];
dp[i][1] += dp[i - 1][1];
}
}
// Count of all valid subsequences
return dp[n][0] + dp[n][1];
}
// Driver Code
int main()
{
int arr[] = { 5, 6, 9, 7 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << validsubsequences(arr, n);
return 0;
}
Java
// Java Program implementation
// of the approach
import java.util.*;
import java.io.*;
class GFG{
// Function to find required subsequences
static int validsubsequences(int arr[], int n)
{
// dp[i][0]: Stores the number of
// subsequences till i-th index
// ending with even element
// dp[i][1]: Stores the number of
// subsequences till i-th index
// ending with odd element
long dp[][] = new long [n + 1][2];
// Initialise the dp[][] with 0.
for(int i = 0; i < n + 1; i++)
{
dp[i][0] = 0;
dp[i][1] = 0;
}
for(int i = 1; i <= n; i++)
{
// If odd element is
// encountered
if (arr[i - 1] % 2 != 0)
{
// Considering i-th element
// will be present in
// the subsequence
dp[i][1] += 1;
// Appending i-th element to all
// non-empty subsequences
// ending with even element
// till (i-1)th indexes
dp[i][1] += dp[i - 1][0];
// Considering ith element will
// not be present in
// the subsequence
dp[i][1] += dp[i - 1][1];
dp[i][0] += dp[i - 1][0];
}
else
{
// Considering i-th element
// will be present in
// the subsequence
dp[i][0] += 1;
// Appending i-th element to all
// non-empty subsequences
// ending with odd element
// till (i-1)th indexes
dp[i][0] += dp[i - 1][1];
// Considering ith element will
// not be present in
// the subsequence
dp[i][0] += dp[i - 1][0];
dp[i][1] += dp[i - 1][1];
}
}
// Count of all valid subsequences
return (int)(dp[n][0] + dp[n][1]);
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 5, 6, 9, 7 };
int n = arr.length;
System.out.print(validsubsequences(arr, n));
}
}
// This code is contributed by code_hunt
Python3
# Python3 program to implement the # above approach # Function to find required subsequences def validsubsequences(arr, n): # dp[i][0]: Stores the number of # subsequences till i-th index # ending with even element # dp[i][1]: Stores the number of # subsequences till i-th index # ending with odd element # Initialise the dp[][] with 0. dp = [[0 for i in range(2)] for j in range(n + 1)] for i in range(1, n + 1): # If odd element is # encountered if(arr[i - 1] % 2): # Considering i-th element # will be present in # the subsequence dp[i][1] += 1 # Appending i-th element to all # non-empty subsequences # ending with even element # till (i-1)th indexes dp[i][1] += dp[i - 1][0] # Considering ith element will # not be present in # the subsequence dp[i][1] += dp[i - 1][1] dp[i][0] += dp[i - 1][0] else: # Considering i-th element # will be present in # the subsequence dp[i][0] += 1 # Appending i-th element to all # non-empty subsequences # ending with odd element # till (i-1)th indexes dp[i][0] += dp[i - 1][1] # Considering ith element will # not be present in # the subsequence dp[i][0] += dp[i - 1][0] dp[i][1] += dp[i - 1][1] # Count of all valid subsequences return dp[n][0] + dp[n][1] # Driver code if __name__ == '__main__': arr = [ 5, 6, 9, 7 ] n = len(arr) print(validsubsequences(arr, n)) # This code is contributed by Shivam Singh
C#
// C# program implementation
// of the approach
using System;
class GFG{
// Function to find required subsequences
static int validsubsequences(int[] arr, int n)
{
// dp[i][0]: Stores the number of
// subsequences till i-th index
// ending with even element
// dp[i][1]: Stores the number of
// subsequences till i-th index
// ending with odd element
long[,] dp = new long [n + 1, 2];
// Initialise the dp[][] with 0.
for(int i = 0; i < n + 1; i++)
{
dp[i, 0] = 0;
dp[i, 1] = 0;
}
for(int i = 1; i <= n; i++)
{
// If odd element is
// encountered
if (arr[i - 1] % 2 != 0)
{
// Considering i-th element
// will be present in
// the subsequence
dp[i, 1] += 1;
// Appending i-th element to all
// non-empty subsequences
// ending with even element
// till (i-1)th indexes
dp[i, 1] += dp[i - 1, 0];
// Considering ith element will
// not be present in
// the subsequence
dp[i, 1] += dp[i - 1, 1];
dp[i, 0] += dp[i - 1, 0];
}
else
{
// Considering i-th element
// will be present in
// the subsequence
dp[i, 0] += 1;
// Appending i-th element to all
// non-empty subsequences
// ending with odd element
// till (i-1)th indexes
dp[i, 0] += dp[i - 1, 1];
// Considering ith element will
// not be present in
// the subsequence
dp[i, 0] += dp[i - 1, 0];
dp[i, 1] += dp[i - 1, 1];
}
}
// Count of all valid subsequences
return (int)(dp[n, 0] + dp[n, 1]);
}
// Driver code
public static void Main()
{
int[] arr = { 5, 6, 9, 7 };
int n = arr.Length;
Console.Write(validsubsequences(arr, n));
}
}
// This code is contributed by chitranayal
Javascript
<script>
// Javascript program for the above approach
// Function to find required subsequences
function validsubsequences(arr, n)
{
// dp[i][0]: Stores the number of
// subsequences till i-th index
// ending with even element
// dp[i][1]: Stores the number of
// subsequences till i-th index
// ending with odd element
let dp = new Array(n + 1);
for (var i = 0; i < dp.length; i++) {
dp[i] = new Array(2);
}
// Initialise the dp[][] with 0.
for(let i = 0; i < n + 1; i++)
{
dp[i][0] = 0;
dp[i][1] = 0;
}
for(let i = 1; i <= n; i++)
{
// If odd element is
// encountered
if (arr[i - 1] % 2 != 0)
{
// Considering i-th element
// will be present in
// the subsequence
dp[i][1] += 1;
// Appending i-th element to all
// non-empty subsequences
// ending with even element
// till (i-1)th indexes
dp[i][1] += dp[i - 1][0];
// Considering ith element will
// not be present in
// the subsequence
dp[i][1] += dp[i - 1][1];
dp[i][0] += dp[i - 1][0];
}
else
{
// Considering i-th element
// will be present in
// the subsequence
dp[i][0] += 1;
// Appending i-th element to all
// non-empty subsequences
// ending with odd element
// till (i-1)th indexes
dp[i][0] += dp[i - 1][1];
// Considering ith element will
// not be present in
// the subsequence
dp[i][0] += dp[i - 1][0];
dp[i][1] += dp[i - 1][1];
}
}
// Count of all valid subsequences
return (dp[n][0] + dp[n][1]);
}
// Driver Code
let arr = [ 5, 6, 9, 7 ];
let n = arr.length;
document.write(validsubsequences(arr, n));
</script>
Producción:
9
Complejidad de tiempo: O(N)
Complejidad de espacio auxiliar: O(N)