Cuente formas de hacer productos de elementos de array incluso mediante reemplazos

Dada una array arr[] que consta de N enteros, la tarea es contar la cantidad de formas de hacer que el producto de los elementos de la array sea parejo reemplazando los elementos de la array cualquier cantidad de veces. Dado que el recuento puede ser muy grande, imprima el módulo de recuento 10 ⁹ +7 .

Ejemplos:

Entrada: arr[] = {1, 3}
Salida: 3
Explicación: 
Operación 1: Reemplazar arr[0] por 2. Por lo tanto, arr[] se modifica a {2, 3}. Producto = 6. 
Operación 2: Reemplazar arr[0] por 10. Por lo tanto, arr[] se modifica a {1, 10}, Producto= 10. 
Operación 3: Reemplazar arr[0] y arr[1] por 2. Por lo tanto, arr[] se modifica a {2, 2}, Producto = 4. 
Por lo tanto, existen 3 formas posibles.

Entrada: arr[] = {3}
Salida: 1 

Enfoque: la idea es usar el enfoque codicioso para resolver este problema.
Siga los pasos a continuación para resolver el problema:

• Para que el producto de la array sea par , debe existir al menos un elemento de array par.
• Atraviesa la array . Para cada elemento de la array, surgen las siguientes dos situaciones: 
  • Si la array consta de un solo elemento, entonces solo existe una única forma de hacer que el producto de la array sea par.
  • De lo contrario, 2 ^N – 1 vías.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to count ways to make
// product of given array even.
void makeProductEven(int arr[], int N)
{
    int m = 1000000007, ans = 1;
 
    // Calculate 2 ^ N
    for (int i = 0; i < N; i++)
    {
        ans = (ans * 2) % m;
    }
 
    // Print the answer
    cout << ans - 1;
}
 
// Driver Code
int main()
{
   
    // Given array
    int arr[] = { 1, 3 };
 
    // Size of the array
    int N = sizeof(arr) / sizeof(arr[0]);
    makeProductEven(arr, N);
    return 0;
}

// Java program for above approach
/*package whatever //do not write package name here */
import java.io.*;
class GFG
{
 
  // Method to count ways to make
  // product of given array even.
  static void makeProductEven(int arr[], int N)
  {
    int m = 1000000007, ans = 1;
 
    // Calculate 2 ^ N
    for (int i = 0; i < N; i++)
    {
      ans = (ans * 2) % m;
    }
 
    // Print the answer
    System.out.println(ans - 1);
  }
  public static void main(String[] args)
  {
 
    // Given array
    int arr[] = { 1, 3 };
 
    // Size of the array
    int N = arr.length;
    makeProductEven(arr, N);
  }
}
 
// This code is contributed by shubham agrawal

# Python3 program for the above approach
 
# Function to count ways to make
# product of given array even.
def makeProductEven(arr, N) :
    m = 1000000007; ans = 1;
 
    # Calculate 2 ^ N
    for i in range(N) :
        ans = (ans * 2) % m;
 
    # Print the answer
    print(ans - 1);
 
# Driver Code
if __name__ == "__main__" :
 
    # Given array
    arr = [ 1, 3 ];
 
    # Size of the array
    N = len(arr);
 
    makeProductEven(arr, N);
 
    # This code is contributed by AnkThon

// C# program for above approach
/*package whatever //do not write package name here */
using System;
public class GFG
{
 
  // Method to count ways to make
  // product of given array even.
  static void makeProductEven(int []arr, int N)
  {
    int m = 1000000007, ans = 1;
 
    // Calculate 2 ^ N
    for (int i = 0; i < N; i++)
    {
      ans = (ans * 2) % m;
    }
 
    // Print the answer
    Console.WriteLine(ans - 1);
  }
   
  // Driver code
  public static void Main(String[] args)
  {
 
    // Given array
    int []arr = { 1, 3 };
 
    // Size of the array
    int N = arr.Length;
    makeProductEven(arr, N);
  }
}
 
// This code is contributed by shikhasingrajput

<script>
 
// Javascript program for the above approach
 
// Function to count ways to make
// product of given array even.
function makeProductEven(arr, N)
{
    var m = 1000000007, ans = 1;
 
    // Calculate 2 ^ N
    for (var i = 0; i < N; i++)
    {
        ans = (ans * 2) % m;
    }
 
    // Print the answer
    document.write( ans - 1);
}
 
// Driver Code
// Given array
var arr = [ 1, 3 ];
// Size of the array
var N = arr.length;
makeProductEven(arr, N);
 
</script>

3

Complejidad de tiempo: O(N)

Espacio Auxiliar: O(1)