Dada una array A[] de tamaño N , la tarea es contar el número de formas de construir una array B[] de tamaño N , de modo que la diferencia absoluta en los mismos elementos indexados debe ser menor o igual a 1 , es decir abs(A[i] – B[i]) ≤ 1 , y el producto de los elementos del arreglo B[] debe ser un número par.
Ejemplos:
Entrada: A[] = { 2, 3 }
Salida: 7
Explicación:
Los valores posibles de la array B[] son { { 1, 2 }, { 1, 4 }, { 2, 2 }, { 2, 4 }, { 3, 2 }, { 3, 4 } }
Por lo tanto, la salida requerida es 7.Entrada: A[] = { 90, 52, 56, 71, 44, 8, 13, 30, 57, 84 }
Salida: 58921
Enfoque: La idea es primero contar el número de formas de construir una array, B[] tal que abs(A[i] – B[i]) <= 1 y luego eliminar aquellas arrays cuyo producto de elementos no es par . número _ Siga los pasos a continuación para resolver el problema:
- Los valores posibles de B[i] tales que abs(A[i] – B[i]) <= 1 son { A[i], A[i] + 1, A[i] – 1 } . Por lo tanto, el recuento total de formas de construir una array, B[] tal que abs(A[i] – B[i]) menor o igual que 1 es 3 N .
- Recorre la array y almacena el recuento de números pares en la array A[] , por ejemplo, X .
- Si A[i] es un número par, entonces (A[i] – 1) y (A[i] + 1) deben ser un número impar . Por lo tanto, el recuento total de formas de construir la array B[] cuyo producto no es un número par es 2 X .
- Finalmente, imprima el valor de ( 3 N – 2 X ).
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 count the ways to construct
// an array, B[] such that abs(A[i] - B[i]) <=1
// and product of elements of B[] is even
void cntWaysConsArray(int A[], int N)
{
// Stores count of arrays B[] such
// that abs(A[i] - B[i]) <=1
int total = 1;
// Stores count of arrays B[] whose
// product of elements is not even
int oddArray = 1;
// Traverse the array
for (int i = 0; i < N; i++) {
// Update total
total = total * 3;
// If A[i] is an even number
if (A[i] % 2 == 0) {
// Update oddArray
oddArray *= 2;
}
}
// Print 3^N - 2^X
cout << total - oddArray << "\n";
}
// Driver Code
int main()
{
int A[] = { 2, 4 };
int N = sizeof(A) / sizeof(A[0]);
cntWaysConsArray(A, N);
return 0;
}
Java
// Java Program to implement the
// above approach
import java.util.*;
class GFG
{
// Function to find count the ways to construct
// an array, B[] such that abs(A[i] - B[i]) <=1
// and product of elements of B[] is even
static void cntWaysConsArray(int A[], int N)
{
// Stores count of arrays B[] such
// that abs(A[i] - B[i]) <=1
int total = 1;
// Stores count of arrays B[] whose
// product of elements is not even
int oddArray = 1;
// Traverse the array
for (int i = 0; i < N; i++)
{
// Update total
total = total * 3;
// If A[i] is an even number
if (A[i] % 2 == 0)
{
// Update oddArray
oddArray *= 2;
}
}
// Print 3^N - 2^X
System.out.println( total - oddArray);
}
// Driver Code
public static void main(String[] args)
{
int A[] = { 2, 4 };
int N = A.length;
cntWaysConsArray(A, N);
}
}
// This code is contributed by code_hunt.
Python3
# Python3 program to implement # the above approach # Function to find count the ways to construct # an array, B[] such that abs(A[i] - B[i]) <=1 # and product of elements of B[] is even def cntWaysConsArray(A, N) : # Stores count of arrays B[] such # that abs(A[i] - B[i]) <=1 total = 1; # Stores count of arrays B[] whose # product of elements is not even oddArray = 1; # Traverse the array for i in range(N) : # Update total total = total * 3; # If A[i] is an even number if (A[i] % 2 == 0) : # Update oddArray oddArray *= 2; # Print 3^N - 2^X print(total - oddArray); # Driver Code if __name__ == "__main__" : A = [ 2, 4 ]; N = len(A); cntWaysConsArray(A, N); # This code is contributed by AnkThon
C#
// C# program to implement the
// above approach
using System;
class GFG{
// Function to find count the ways to construct
// an array, []B such that abs(A[i] - B[i]) <=1
// and product of elements of []B is even
static void cntWaysConsArray(int []A, int N)
{
// Stores count of arrays []B such
// that abs(A[i] - B[i]) <=1
int total = 1;
// Stores count of arrays []B whose
// product of elements is not even
int oddArray = 1;
// Traverse the array
for(int i = 0; i < N; i++)
{
// Update total
total = total * 3;
// If A[i] is an even number
if (A[i] % 2 == 0)
{
// Update oddArray
oddArray *= 2;
}
}
// Print 3^N - 2^X
Console.WriteLine(total - oddArray);
}
// Driver Code
public static void Main(String[] args)
{
int []A = { 2, 4 };
int N = A.Length;
cntWaysConsArray(A, N);
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// Javascript Program to implement the
// above approach
// Function to find count the ways to construct
// an array, B such that abs(A[i] - B[i]) <=1
// and product of elements of B is even
function cntWaysConsArray(A, N)
{
// Stores count of arrays B such
// that abs(A[i] - B[i]) <=1
var total = 1;
// Stores count of arrays B whose
// product of elements is not even
var oddArray = 1;
// Traverse the array
for(i = 0; i < N; i++)
{
// Update total
total = total * 3;
// If A[i] is an even number
if (A[i] % 2 == 0)
{
// Update oddArray
oddArray *= 2;
}
}
// Print var 3^N - 2^X
document.write(total - oddArray);
}
// Driver Code
var A = [ 2, 4 ];
var N = A.length;
cntWaysConsArray(A, N);
// This code is contributed by umadevi9616
</script>
Producción:
5
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por dhanajitkapali y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA