Dados tres enteros positivos N , L y R . La tarea es encontrar el número de formas de formar una array de tamaño N donde cada elemento se encuentra en el rango [L, R] tal que la suma total de todos los elementos de la array sea divisible por 2 .
Ejemplos:
Entrada: N = 2, L = 1, R = 3
Salida: 5
Las posibles arrays que tienen la suma de todos los elementos divisibles por 2 son
[1, 1], [2, 2], [1, 3], [3, 1] y [3, 3]
Entrada: N = 3, L = 2, R = 2
Salida: 1
Enfoque: La idea es encontrar el conteo de números que tienen resto 0 y 1 módulo 2 separados entre L y R. Este conteo se puede calcular de la siguiente manera:
Necesitamos contar números entre rangos que tengan resto 1 módulo 2
F = Primer número en el rango del tipo requerido
L = Último número en el rango del tipo requerido
Count = (L – F) / 2
cnt0, y cnt1 representa Count of number between range of cada tipo.
Entonces, usando programación dinámica podemos resolver este problema. Sea dp[i][j] el número de formas en que la suma de los primeros i números módulo 2 es igual a j. Supongamos que necesitamos calcular dp[i][0], entonces tendrá la siguiente relación de recurrencia: dp[i][0] = (cnt0 * dp[i – 1][0] + cnt1 * dp[i – 1 ][1]) . El primer término representa el número de caminos hasta (i – 1) con un resto de suma igual a 0, por lo que podemos colocar cnt0 números en i -ésima posición de manera que el resto de suma siga siendo 0. El segundo término representa el número de caminos hasta (i – 1) teniendo el resto de la suma como 1, entonces podemos colocar los números cnt1 en la i -ésima posición para que el resto de la suma sea 0. De manera similar, podemos calcular para dp[i][1].
La respuesta final se denotará pordp[N][0] .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the number of ways to
// form an array of size n such that sum of
// all elements is divisible by 2
int countWays(int n, int l, int r)
{
int tL = l, tR = r;
// Represents first and last numbers
// of each type (modulo 0 and 1)
int L[2] = { 0 }, R[2] = { 0 };
L[l % 2] = l, R[r % 2] = r;
l++, r--;
if (l <= tR && r >= tL)
L[l % 2] = l, R[r % 2] = r;
// Count of numbers of each type between range
int cnt0 = 0, cnt1 = 0;
if (R[0] && L[0])
cnt0 = (R[0] - L[0]) / 2 + 1;
if (R[1] && L[1])
cnt1 = (R[1] - L[1]) / 2 + 1;
int dp[n][2];
// Base Cases
dp[1][0] = cnt0;
dp[1][1] = cnt1;
for (int i = 2; i <= n; i++) {
// Ways to form array whose sum upto
// i numbers modulo 2 is 0
dp[i][0] = (cnt0 * dp[i - 1][0]
+ cnt1 * dp[i - 1][1]);
// Ways to form array whose sum upto
// i numbers modulo 2 is 1
dp[i][1] = (cnt0 * dp[i - 1][1]
+ cnt1 * dp[i - 1][0]);
}
// Return the required count of ways
return dp[n][0];
}
// Driver Code
int main()
{
int n = 2, l = 1, r = 3;
cout << countWays(n, l, r);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
// Function to return the number of ways to
// form an array of size n such that sum of
// all elements is divisible by 2
static int countWays(int n, int l, int r)
{
int tL = l, tR = r;
// Represents first and last numbers
// of each type (modulo 0 and 1)
int[] L = new int[3];
int[] R = new int[3];
L[l % 2] = l;
R[r % 2] = r;
l++;
r--;
if (l <= tR && r >= tL)
{
L[l % 2] = l;
R[r % 2] = r;
}
// Count of numbers of each type between range
int cnt0 = 0, cnt1 = 0;
if (R[0] > 0 && L[0] > 0)
cnt0 = (R[0] - L[0]) / 2 + 1;
if (R[1] > 0 && L[1] > 0)
cnt1 = (R[1] - L[1]) / 2 + 1;
int[][] dp = new int[n + 1][3];
// Base Cases
dp[1][0] = cnt0;
dp[1][1] = cnt1;
for (int i = 2; i <= n; i++)
{
// Ways to form array whose sum upto
// i numbers modulo 2 is 0
dp[i][0] = (cnt0 * dp[i - 1] [0]
+ cnt1 * dp[i - 1][1]);
// Ways to form array whose sum upto
// i numbers modulo 2 is 1
dp[i][1] = (cnt0 * dp[i - 1][1]
+ cnt1 * dp[i - 1][0]);
}
// Return the required count of ways
return dp[n][0];
}
// Driver Code
public static void main(String[] args)
{
int n = 2, l = 1, r = 3;
System.out.println(countWays(n, l, r));
}
}
// This code is contributed by Code_Mech.
Python3
# Python3 implementation of the approach # Function to return the number of ways to # form an array of size n such that sum of # all elements is divisible by 2 def countWays(n, l, r): tL, tR = l, r # Represents first and last numbers # of each type (modulo 0 and 1) L = [0 for i in range(2)] R = [0 for i in range(2)] L[l % 2] = l R[r % 2] = r l += 1 r -= 1 if (l <= tR and r >= tL): L[l % 2], R[r % 2] = l, r # Count of numbers of each type # between range cnt0, cnt1 = 0, 0 if (R[0] and L[0]): cnt0 = (R[0] - L[0]) // 2 + 1 if (R[1] and L[1]): cnt1 = (R[1] - L[1]) // 2 + 1 dp = [[0 for i in range(2)] for i in range(n + 1)] # Base Cases dp[1][0] = cnt0 dp[1][1] = cnt1 for i in range(2, n + 1): # Ways to form array whose sum # upto i numbers modulo 2 is 0 dp[i][0] = (cnt0 * dp[i - 1][0] + cnt1 * dp[i - 1][1]) # Ways to form array whose sum upto # i numbers modulo 2 is 1 dp[i][1] = (cnt0 * dp[i - 1][1] + cnt1 * dp[i - 1][0]) # Return the required count of ways return dp[n][0] # Driver Code n, l, r = 2, 1, 3 print(countWays(n, l, r)) # This code is contributed # by Mohit Kumar
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to return the number of ways to
// form an array of size n such that sum of
// all elements is divisible by 2
static int countWays(int n, int l, int r)
{
int tL = l, tR = r;
// Represents first and last numbers
// of each type (modulo 0 and 1)
int[] L = new int[3];
int[] R = new int[3];
L[l % 2] = l;
R[r % 2] = r;
l++;
r--;
if (l <= tR && r >= tL)
{
L[l % 2] = l;
R[r % 2] = r;
}
// Count of numbers of each type between range
int cnt0 = 0, cnt1 = 0;
if (R[0] > 0 && L[0] > 0)
cnt0 = (R[0] - L[0]) / 2 + 1;
if (R[1] > 0 && L[1] > 0)
cnt1 = (R[1] - L[1]) / 2 + 1;
int[,] dp=new int[n + 1, 3];
// Base Cases
dp[1, 0] = cnt0;
dp[1, 1] = cnt1;
for (int i = 2; i <= n; i++)
{
// Ways to form array whose sum upto
// i numbers modulo 2 is 0
dp[i, 0] = (cnt0 * dp[i - 1, 0]
+ cnt1 * dp[i - 1, 1]);
// Ways to form array whose sum upto
// i numbers modulo 2 is 1
dp[i, 1] = (cnt0 * dp[i - 1, 1]
+ cnt1 * dp[i - 1, 0]);
}
// Return the required count of ways
return dp[n, 0];
}
// Driver Code
static void Main()
{
int n = 2, l = 1, r = 3;
Console.WriteLine(countWays(n, l, r));
}
}
// This code is contributed by mits
PHP
<?php
// PHP implementation of the approach
// Function to return the number of ways to
// form an array of size n such that sum of
// all elements is divisible by 2
function countWays($n, $l, $r)
{
$tL = $l;
$tR = $r;
$L = array_fill(0, 2, 0);
$R = array_fill(0, 2, 0);
// Represents first and last numbers
// of each type (modulo 0 and 1)
$L[$l % 2] = $l;
$R[$r % 2] = $r;
$l++;
$r--;
if ($l <= $tR && $r >= $tL)
{
$L[$l % 2] = $l;
$R[$r % 2] = $r;
}
// Count of numbers of each type
// between range
$cnt0 = 0;
$cnt1 = 0;
if ($R[0] && $L[0])
$cnt0 = ($R[0] - $L[0]) / 2 + 1;
if ($R[1] && $L[1])
$cnt1 = ($R[1] - $L[1]) / 2 + 1;
$dp = array();
// Base Cases
$dp[1][0] = $cnt0;
$dp[1][1] = $cnt1;
for ($i = 2; $i <= $n; $i++)
{
// Ways to form array whose sum upto
// i numbers modulo 2 is 0
$dp[$i][0] = ($cnt0 * $dp[$i - 1][0] +
$cnt1 * $dp[$i - 1][1]);
// Ways to form array whose sum upto
// i numbers modulo 2 is 1
$dp[$i][1] = ($cnt0 * $dp[$i - 1][1] +
$cnt1 * $dp[$i - 1][0]);
}
// Return the required count of ways
return $dp[$n][0];
}
// Driver Code
$n = 2;
$l = 1;
$r = 3;
echo countWays($n, $l, $r);
// This code is contributed by Ryuga
?>
Javascript
<script>
// JavaScript implementation of the approach
// Function to return the number of ways to
// form an array of size n such that sum of
// all elements is divisible by 2
function countWays(n, l, r)
{
let tL = l, tR = r;
// Represents first and last numbers
// of each type (modulo 0 and 1)
let L = new Array(3);
let R = new Array(3);
L[l % 2] = l;
R[r % 2] = r;
l++;
r--;
if (l <= tR && r >= tL)
{
L[l % 2] = l;
R[r % 2] = r;
}
// Count of numbers of each type between range
let cnt0 = 0, cnt1 = 0;
if (R[0] > 0 && L[0] > 0)
cnt0 = (R[0] - L[0]) / 2 + 1;
if (R[1] > 0 && L[1] > 0)
cnt1 = (R[1] - L[1]) / 2 + 1;
let dp = new Array(n + 1);
for (let i = 0; i <= n; i++)
{
dp[i] = new Array(3);
for (let j = 0; j < 3; j++)
{
dp[i][j] = 0;
}
}
// Base Cases
dp[1][0] = cnt0;
dp[1][1] = cnt1;
for (let i = 2; i <= n; i++)
{
// Ways to form array whose sum upto
// i numbers modulo 2 is 0
dp[i][0] = (cnt0 * dp[i - 1] [0]
+ cnt1 * dp[i - 1][1]);
// Ways to form array whose sum upto
// i numbers modulo 2 is 1
dp[i][1] = (cnt0 * dp[i - 1][1]
+ cnt1 * dp[i - 1][0]);
}
// Return the required count of ways
return dp[n][0];
}
let n = 2, l = 1, r = 3;
document.write(countWays(n, l, r));
</script>
5
Complejidad de tiempo: O(n)
Espacio Auxiliar: O(n)
Publicación traducida automáticamente
Artículo escrito por Nishant Tanwar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA