Dada una array arr[] que consta de N enteros impares, la tarea es contar las diferentes formas de hacer que el producto de todos los elementos de la array sea par, cambiando repetidamente cualquier conjunto de elementos a cualquier valor. Dado que el conteo puede ser muy grande, imprímalo en módulo 10 9 + 7 .
Ejemplos:
Entrada: arr[] = {1, 3}
Salida: 3
Explicación: Todas las formas posibles de hacer que el producto de los elementos de un arreglo sea impar son las siguientes:
Reemplace arr[0] por cualquier número entero par. La array arr[] se modifica a {par, 3}. Por lo tanto, el producto del arreglo = par * 3 = par.
Reemplace arr[1] por cualquier número entero par. La array arr[] se modifica a {1, even}. Por lo tanto, el producto del arreglo = 1 * par = par.
Reemplace arr[0] y arr[1] por números enteros pares. Dado que ambos elementos del arreglo se vuelven pares, el producto del arreglo se vuelve par. Por lo tanto, el número total de formas distintas de hacer que el arreglo sea par es 3.Entrada: arr[] = {1, 2, 3, 4, 5}
Salida: 31
Enfoque: La idea para resolver el problema dado se basa en la observación de que el producto de un arreglo es par solo cuando al menos un elemento par está presente en el arreglo . Por lo tanto, el número total de formas distintas se puede calcular por el número de subconjuntos distintos de la array dada .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
#define M 1000000007
using namespace std;
// Function to find the value of (x^y)
long long power(long long x, long long y,
long long p)
{
// Stores the result
long long res = 1;
while (y > 0) {
// If y is odd, then
// multiply x with res
if (y & 1)
res = (res * x) % p;
// y must be even now
y = y >> 1;
// Update x
x = (x * x) % p;
}
return res;
}
// Function to count the number of ways
// to make the product of an array even
// by replacing array elements
int totalOperations(int arr[], int N)
{
// Find the value ( 2 ^ N ) % M
long long res = power(2, N, M);
// Exclude empty subset
res--;
// Print the answer
cout << res;
}
// Driver Code
int main()
{
int arr[] = { 1, 2, 3, 4, 5 };
int N = sizeof(arr) / sizeof(arr[0]);
totalOperations(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
class GFG{
static long M = 1000000007;
// Function to find the value of (x^y)
static long power(long x, long y, long p)
{
// Stores the result
long res = 1;
while (y > 0)
{
// If y is odd, then
// multiply x with res
if ((y & 1) > 0)
res = (res * x) % p;
// y must be even now
y = y >> 1;
// Update x
x = (x * x) % p;
}
return res;
}
// Function to count the number of ways
// to make the product of an array even
// by replacing array elements
static int totalOperations(int arr[], int N)
{
// Find the value ( 2 ^ N ) % M
long res = power(2, N, M);
// Exclude empty subset
res--;
// Print the answer
System.out.print(res);
return 0;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 1, 2, 3, 4, 5 };
int N = arr.length;
totalOperations(arr, N);
}
}
// This code is contributed by rag2127
Python3
# Python3 program for the above approach M = 1000000007 # Function to find the value of (x^y) def power(x, y, p): global M # Stores the result res = 1 while (y > 0): # If y is odd, then # multiply x with res if (y & 1): res = (res * x) % p; # y must be even now y = y >> 1 # Update x x = (x * x) % p return res # Function to count the number of ways # to make the product of an array even # by replacing array elements def totalOperations(arr, N): # Find the value ( 2 ^ N ) % M res = power(2, N, M) # Exclude empty subset res-=1 # Print the answer print (res) # Driver Code if __name__ == '__main__': arr = [1, 2, 3, 4, 5] N = len(arr) totalOperations(arr, N) # This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
class GFG {
static long M = 1000000007;
// Function to find the value of (x^y)
static long power(long x, long y, long p)
{
// Stores the result
long res = 1;
while (y > 0)
{
// If y is odd, then
// multiply x with res
if ((y & 1) > 0)
res = (res * x) % p;
// y must be even now
y = y >> 1;
// Update x
x = (x * x) % p;
}
return res;
}
// Function to count the number of ways
// to make the product of an array even
// by replacing array elements
static int totalOperations(int[] arr, int N)
{
// Find the value ( 2 ^ N ) % M
long res = power(2, N, M);
// Exclude empty subset
res--;
// Print the answer
Console.Write(res);
return 0;
}
// Calculating gcd
static int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// Driver code
static void Main()
{
int[] arr = { 1, 2, 3, 4, 5 };
int N = arr.Length;
totalOperations(arr, N);
}
}
// This code is contributed by sanjoy_62.
Javascript
<script>
let M = 1000000007;
// Function to find the value of (x^y)
function power(x,y,p)
{
// Stores the result
let res = 1;
while (y > 0)
{
// If y is odd, then
// multiply x with res
if ((y & 1) > 0)
res = (res * x) % p;
// y must be even now
y = y >> 1;
// Update x
x = (x * x) % p;
}
return res;
}
// Function to count the number of ways
// to make the product of an array even
// by replacing array elements
function totalOperations(arr,N)
{
// Find the value ( 2 ^ N ) % M
let res = power(2, N, M);
// Exclude empty subset
res--;
// Print the answer
document.write(res);
}
// Driver Code
let arr=[ 1, 2, 3, 4, 5];
let N = arr.length;
totalOperations(arr, N);
// This code is contributed by avanitrachhadiya2155
</script>
31
Complejidad temporal: O(log N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por koulick_sadhu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA