Dado un entero par positivo ‘n’. Cuente el número total de formas de expresar ‘n’ como suma de números enteros positivos pares. Salida de la respuesta en módulo 10 9 + 7
Ejemplos:
Input: 6 Output: 4 Explanation There are only four ways to write 6 as sum of even integers: 1. 2 + 2 + 2 2. 2 + 4 3. 4 + 2 4. 6 Input: 8 Output: 8
El enfoque es encontrar un patrón o una función recursiva, lo que sea posible. El enfoque sería el mismo que ya se discutió en “ Contar formas de expresar ‘n’ como suma de enteros impares ”. Aquí el número dado es par, lo que significa que la suma par solo se puede lograr sumando el (n-2) número como dos veces. Podemos notar que (tomando algunos ejemplos) agregar un 2 a un número duplica la cuenta. Deje que el número total de formas de escribir ‘n’ sea formas (n). El valor de ‘vías (n)’ se puede escribir mediante la fórmula de la siguiente manera:
ways(n) = ways(n-2) + ways(n-2) ways(n) = 2 * ways(n-2) ways(2) = 1 = 20 ways(4) = 2 = 21 ways(6) = 4 = 22 ways(8) = 8 = 23 '' '' '' ways(2 * n) = 2n-1 Replace n by (m / 2) => ways(m) = 2m/2 - 1
C++
// C++ program to count ways to write
// number as sum of even integers
#include<iostream>
using namespace std;
// Initialize mod variable as constant
const int MOD = 1e9 + 7;
/* Iterative Function to calculate (x^y)%p in O(log y) */
int power(int x, unsigned int y, int p)
{
int res = 1; // Initialize result
x = x % p; // Update x if it is more than or
// equal to p
while (y > 0)
{
// If y is odd, multiply x with result
if (y & 1)
res = (1LL * res * x) % p;
// y must be even now
y = y>>1; // y = y/2
x = (1LL * x * x) % p;
}
return res;
}
// Return number of ways to write 'n'
// as sum of even integers
int countEvenWays(int n)
{
return power(2, n/2 - 1, MOD);
}
// Driver code
int main()
{
int n = 6;
cout << countEvenWays(n) << "\n";
n = 8;
cout << countEvenWays(n);
return 0;
}
Java
// JAVA program to count ways to write
// number as sum of even integers
class GFG {
// Initialize mod variable as constant
static int MOD = 1000000007;
/* Iterative Function to calculate
(x^y)%p in O(log y) */
static int power(int x, int y, int p)
{
// Initialize result
int res = 1;
// Update x if it is more
// than or equal to p
x = x % p;
while (y > 0)
{
// If y is odd, multiply x
// with result
if (y % 2 == 1)
res = (1 * res * x) % p;
// y must be even now
y = y >> 1; // y = y/2
x = (1 * x * x) % p;
}
return res;
}
// Return number of ways to write
// 'n' as sum of even integers
static int countEvenWays(int n)
{
return power(2, n/2 - 1, MOD);
}
// Driver code
public static void main(String args[])
{
int n = 6;
System.out.println(countEvenWays(n));
n = 8;
System.out.println(countEvenWays(n));
}
}
/* This code is contributed by Nikita Tiwari. */
Python
# PYTHON program to count ways to write # number as sum of even integers # Initialize mod variable as constant MOD = 1e9 + 7 # Iterative Function to calculate # (x^y)%p in O(log y) def power(x, y, p) : res = 1 # Initialize result x = x % p # Update x if it is more # than or equal to p while (y > 0) : # If y is odd, multiply x # with result if (y & 1) : res = (1 * res * x) % p # y must be even now y = y >> 1 # y = y/2 x = (1 * x * x) % p return res # Return number of ways to write 'n' # as sum of even integers def countEvenWays(n) : return power(2, n/2 - 1, MOD) # Driver code n = 6 print (int(countEvenWays(n))) n = 8 print (int(countEvenWays(n))) # This code is contributed by Nikita Tiwari.
C#
// C# program to count ways to write
// number as sum of even integers
using System;
class GFG {
// Initialize mod variable as constant
static int MOD = 1000000007;
/* Iterative Function to calculate
(x^y)%p in O(log y) */
static int power(int x, int y, int p)
{
// Initialize result
int res = 1;
// Update x if it is more
// than or equal to p
x = x % p;
while (y > 0)
{
// If y is odd, multiply x
// with result
if (y % 2 == 1)
res = (1 * res * x) % p;
// y must be even now
y = y >> 1; // y = y/2
x = (1 * x * x) % p;
}
return res;
}
// Return number of ways to write
// 'n' as sum of even integers
static int countEvenWays(int n)
{
return power(2, n/2 - 1, MOD);
}
// Driver code
public static void Main()
{
int n = 6;
Console.WriteLine(countEvenWays(n));
n = 8;
Console.WriteLine(countEvenWays(n));
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP program to count ways
// to write number as sum of
// even integers
// Initialize mod variable
// as constant
$MOD = 1000000000.0;
/* Iterative Function to
calculate (x^y)%p in O(log y) */
function power($x, $y, $p)
{
// Initialize result
$res = 1;
// Update x if it is more
// than or equal to p
$x = $x % $p;
while ($y > 0)
{
// If y is odd, multiply
// x with result
if ($y & 1)
$res = (1 * $res *
$x) % $p;
// y must be even now
$y = $y >> 1; // y = y/2
$x = (1 * $x *
$x) % $p;
}
return $res;
}
// Return number of ways
// to write 'n' as sum of
// even integers
function countEvenWays($n)
{
global $MOD;
return power(2, $n /
2 - 1, $MOD);
}
// Driver code
$n = 6;
echo countEvenWays($n), "\n";
$n = 8;
echo countEvenWays($n);
// This code is contributed
// by ajit
?>
Javascript
<script>
// Javascript program to count ways to write
// number as sum of even integers
// Initialize mod variable as constant
let MOD = 1000000007;
/* Iterative Function to calculate
(x^y)%p in O(log y) */
function power(x, y, p)
{
// Initialize result
let res = 1;
// Update x if it is more
// than or equal to p
x = x % p;
while (y > 0)
{
// If y is odd, multiply x
// with result
if (y % 2 == 1)
res = (1 * res * x) % p;
// y must be even now
y = y >> 1; // y = y/2
x = (1 * x * x) % p;
}
return res;
}
// Return number of ways to write
// 'n' as sum of even integers
function countEvenWays(n)
{
return power(2, n/2 - 1, MOD);
}
// Driver code
let n = 6;
document.write(countEvenWays(n) + "<br/>");
n = 8;
document.write(countEvenWays(n));
// This code is contributed by code_hunt.
</script>
Producción:
4 8
Complejidad temporal: O(Log(n))
Espacio auxiliar: O(1)
Este artículo es una contribución de Shubham Bansal . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA