Dada una array arr[] de tamaño N , la tarea es contar el número de formas en que podemos seleccionar un subconjunto de los elementos de array dados, de modo que la mediana del subconjunto seleccionado también esté presente como un elemento en el subconjunto. Dado que este número puede ser grande, calcúlelo módulo 1000000007.
Ejemplos:
Entrada: arr[] = {2, 3, 2}
Salida: 5
{2}, {3}, {2}, {2, 2} y {2, 3, 2} son todos posibles subconjuntos válidos.
Entrada: arr[] = {1, 4, 2, 2, 3, 5}
Salida: 36
Acercarse:
- Todo subconjunto de tamaño impar tiene su mediana presente en el subconjunto, por lo que podemos sumar directamente 2 N – 1 a la respuesta.
- Para un subconjunto de tamaño par, se seleccionará el subconjunto, si y solo si los dos elementos del medio son iguales.
- Necesitamos contar el número de subconjuntos de tamaño par con elementos intermedios iguales.
La solución Simple sería iterar sobre cada par de elementos iguales (i, j) tal que A[i] = A[j] e iterar sobre el tamaño 2 * X de un subconjunto de X = 1 a N. El número de formas de hacer el subconjunto de tamaño X con dos elementos medios fijos es solo el producto de la cantidad de formas en que podemos seleccionar X – 1 elemento de [1, i – 1] y X – 1 elemento de [j + 1, N] .
Esta solución requiere iterar sobre cada par (i, j) lo que requiere tiempo O(N 2 ) y tiempo O(N) por par, lo que lleva a una complejidad de tiempo total O(N 3 )
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <algorithm>
#include <iostream>
using namespace std;
long long mod = 1000000007;
// Function to return the factorial of a number
int fact(int n)
{
int res = 1;
for (int i = 2; i <= n; i++)
res = res * i;
return res;
}
// Function to return the value of nCr
int nCr(int n, int r)
{
return fact(n) / (fact(r) * fact(n - r));
}
// Function to return a raised to the power n
// with complexity O(log(n))
long long powmod(long long a, long long n)
{
if (!n)
return 1;
long long pt = powmod(a, n / 2);
pt = (pt * pt) % mod;
if (n % 2)
return (pt * a) % mod;
else
return pt;
}
// Function to return the number of sub-sets
// whose median is also present in the set
long long CountSubset(int* arr, int n)
{
// Number of odd length sub-sets
long long ans = powmod(2, n - 1);
// Sort the array
sort(arr, arr + n);
for (int i = 0; i < n; ++i) {
int j = i + 1;
// Checking each element for leftmost middle
// element while they are equal
while (j < n && arr[j] == arr[i]) {
// Calculate the number of elements in
// right of rightmost middle element
int r = n - 1 - j;
// Calculate the number of elements in
// left of leftmost middle element
int l = i;
// Add selected even length subsets
// to the answer
ans = (ans + nCr(l + r, l)) % mod;
j++;
}
}
return ans;
}
// Driver code
int main()
{
int arr[] = { 2, 3, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << CountSubset(arr, n) << endl;
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG {
static long mod = 1000000007;
// Function to return the factorial of a number
static int fact(int n)
{
int res = 1;
for (int i = 2; i <= n; i++)
res = res * i;
return res;
}
// Function to return the value of nCr
static int nCr(int n, int r)
{
return fact(n) / (fact(r) * fact(n - r));
}
// Function to return a raised to the power n
// with complexity O(log(n))
static long powmod(long a, long n)
{
if (n == 0)
return 1;
long pt = powmod(a, n / 2);
pt = (pt * pt) % mod;
if (n % 2 == 1)
return (pt * a) % mod;
else
return pt;
}
// Function to return the number of sub-sets
// whose median is also present in the set
static long CountSubset(int[] arr, int n)
{
// Number of odd length sub-sets
long ans = powmod(2, n - 1);
// Sort the array
Arrays.sort(arr);
for (int i = 0; i < n; ++i) {
int j = i + 1;
// Checking each element for leftmost middle
// element while they are equal
while (j < n && arr[j] == arr[i]) {
// Calculate the number of elements in
// right of rightmost middle element
int r = n - 1 - j;
// Calculate the number of elements in
// left of leftmost middle element
int l = i;
// Add selected even length subsets
// to the answer
ans = (ans + nCr(l + r, l)) % mod;
j++;
}
}
return ans;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 2, 3, 2 };
int n = arr.length;
System.out.println(CountSubset(arr, n));
}
}
// This code has been contributed by 29AjayKumar
Python3
# Python 3 implementation of the approach mod = 1000000007 # Function to return # the factorial of a number def fact(n): res = 1 for i in range(2, n + 1): res = res * i return res # Function to return the value of nCr def nCr(n, r): return int(fact(n) / (fact(r) * fact(n - r))) # Function to return 'a' raised to the power n # with complexity O(log(n)) def powmod(a, n): if (n == 0): return 1 pt = powmod(a, int(n / 2)) pt = (pt * pt) % mod if (n % 2): return (pt * a) % mod else: return pt # Function to return the number of sub-sets # whose median is also present in the set def CountSubset(arr, n): # Number of odd length sub-sets ans = powmod(2, n - 1) # Sort the array arr.sort(reverse = False) for i in range(n): j = i + 1 # Checking each element for leftmost middle # element while they are equal while (j < n and arr[j] == arr[i]): # Calculate the number of elements in # right of rightmost middle element r = n - 1 - j # Calculate the number of elements in # left of leftmost middle element l = i # Add selected even length subsets # to the answer ans = (ans + nCr(l + r, l)) % mod j += 1 return ans # Driver code if __name__ == '__main__': arr = [2, 3, 2] n = len(arr) print(CountSubset(arr, n)) # This code is contributed by # Surendra_Gangwar
C#
// C# implementation of the approach
using System;
class GFG {
static long mod = 1000000007;
// Function to return the factorial of a number
static int fact(int n)
{
int res = 1;
for (int i = 2; i <= n; i++)
res = res * i;
return res;
}
// Function to return the value of nCr
static int nCr(int n, int r)
{
return fact(n) / (fact(r) * fact(n - r));
}
// Function to return a raised to the power n
// with complexity O(log(n))
static long powmod(long a, long n)
{
if (n == 0)
return 1;
long pt = powmod(a, n / 2);
pt = (pt * pt) % mod;
if (n % 2 == 1)
return (pt * a) % mod;
else
return pt;
}
// Function to return the number of sub-sets
// whose median is also present in the set
static long CountSubset(int[] arr, int n)
{
// Number of odd length sub-sets
long ans = powmod(2, n - 1);
// Sort the array
Array.Sort(arr);
for (int i = 0; i < n; ++i) {
int j = i + 1;
// Checking each element for leftmost middle
// element while they are equal
while (j < n && arr[j] == arr[i]) {
// Calculate the number of elements in
// right of rightmost middle element
int r = n - 1 - j;
// Calculate the number of elements in
// left of leftmost middle element
int l = i;
// Add selected even length subsets
// to the answer
ans = (ans + nCr(l + r, l)) % mod;
j++;
}
}
return ans;
}
// Driver code
public static void Main(String[] args)
{
int[] arr = { 2, 3, 2 };
int n = arr.Length;
Console.WriteLine(CountSubset(arr, n));
}
}
// This code has been contributed by 29AjayKumar
PHP
<?php
// PHP implementation of the approach
$mod = 1000000007;
// Function to return the factorial of a number
function fact($n)
{
$res = 1;
for ($i = 2; $i <= $n; $i++)
$res = $res * $i;
return $res;
}
// Function to return the value of nCr
function nCr($n, $r)
{
return fact($n) / (fact($r) * fact($n - $r));
}
// Function to return a raised to the power n
// with complexity O(log(n))
function powmod($a, $n)
{
global $mod;
if ($n == 0)
return 1;
$pt = powmod($a, $n / 2);
$pt = ($pt * $pt) % $mod;
if ($n % 2 == 1)
return ($pt * $a) % $mod;
else
return $pt;
}
// Function to return the number of sub-sets
// whose median is also present in the set
function CountSubset( $arr, $n)
{
global $mod;
// Number of odd length sub-sets
$ans = powmod(2, $n - 1);
// Sort the array
sort($arr, 0);
for ($i = 0; $i < $n; ++$i)
{
$j = $i + 1;
// Checking each element for leftmost middle
// element while they are equal
while ($j < $n && $arr[$j] == $arr[$i])
{
// Calculate the number of elements in
// right of rightmost middle element
$r = $n - 1 - $j;
// Calculate the number of elements in
// left of leftmost middle element
$l = $i;
// Add selected even length subsets
// to the answer
$ans = ($ans + nCr($l + $r, $l)) % $mod;
$j++;
}
}
return $ans;
}
// Driver code
{
$arr = array(2, 3, 2 );
$n = sizeof($arr);
echo(CountSubset($arr, $n));
}
// This code has been contributed by Code_Mech.
Javascript
<script>
// JavaScript implementation of the approach
const mod = 1000000007;
// Function to return the factorial of a number
function fact(n)
{
let res = 1;
for (let i = 2; i <= n; i++)
res = res * i;
return res;
}
// Function to return the value of nCr
function nCr(n, r)
{
return parseInt(fact(n) / (fact(r) * fact(n - r)));
}
// Function to return a raised to the power n
// with complexity O(log(n))
function powmod(a, n)
{
if (!n)
return 1;
let pt = powmod(a, parseInt(n / 2));
pt = (pt * pt) % mod;
if (n % 2)
return (pt * a) % mod;
else
return pt;
}
// Function to return the number of sub-sets
// whose median is also present in the set
function CountSubset(arr, n)
{
// Number of odd length sub-sets
let ans = powmod(2, n - 1);
// Sort the array
arr.sort();
for (let i = 0; i < n; ++i) {
let j = i + 1;
// Checking each element for leftmost middle
// element while they are equal
while (j < n && arr[j] == arr[i]) {
// Calculate the number of elements in
// right of rightmost middle element
let r = n - 1 - j;
// Calculate the number of elements in
// left of leftmost middle element
let l = i;
// Add selected even length subsets
// to the answer
ans = (ans + nCr(l + r, l)) % mod;
j++;
}
}
return ans;
}
// Driver code
let arr = [ 2, 3, 2 ];
let n = arr.length;
document.write(CountSubset(arr, n));
</script>
Producción:
5
Complejidad de tiempo: O(N 3 ), ya que estamos usando bucles anidados para atravesar N*N veces y en cada recorrido estamos llamando a la función NCR que cuesta O(N). Donde N es el número de elementos de la array.
Espacio auxiliar: O(1), ya que no estamos utilizando ningún espacio adicional.
La complejidad temporal del enfoque anterior se puede reducir a O(N 2 ) si almacenamos el triángulo pascal en una array bidimensional. Entonces, ahora no tenemos que calcular el factorial una y otra vez. Lea más sobre el triángulo de Pascal aquí .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <algorithm>
#include <iostream>
using namespace std;
long long mod = 1000000007;
long long arr[1001][1001];
// Function to store pascal triangle in 2-d array
void Preprocess()
{
arr[0][0] = 1;
for (int i = 1; i <= 1000; ++i) {
arr[i][0] = 1;
for (int j = 1; j < i; ++j) {
arr[i][j] = (arr[i - 1][j - 1] + arr[i - 1][j]) % mod;
}
arr[i][i] = 1;
}
}
// Function to return a raised to the power n
// with complexity O(log(n))
long long powmod(long long a, long long n)
{
if (!n)
return 1;
long long pt = powmod(a, n / 2);
pt = (pt * pt) % mod;
if (n % 2)
return (pt * a) % mod;
else
return pt;
}
// Function to return the number of sub-sets
// whose median is also present in the set
long long CountSubset(int* val, int n)
{
// Number of odd length sub-sets
long long ans = powmod(2, n - 1);
// Sort the array
sort(val, val + n);
for (int i = 0; i < n; ++i) {
int j = i + 1;
// Checking each element for leftmost middle
// element while they are equal
while (j < n && val[j] == val[i]) {
// Calculate the number of elements in
// right of rightmost middle element
int r = n - 1 - j;
// Calculate the number of elements in
// left of leftmost middle element
int l = i;
// Add selected even length subsets
// to the answer
ans = (ans + arr[l + r][l]) % mod;
j++;
}
}
return ans;
}
// Driver code
int main()
{
Preprocess();
int val[] = { 2, 3, 2 };
int n = sizeof(val) / sizeof(val[0]);
cout << CountSubset(val, n) << endl;
return 0;
}
Java
// Java implementation of the above approach
import java.util.Arrays;
class GFG
{
static long mod = 1000000007;
static long[][] arr = new long[1001][1001];
// Function to store pascal triangle in 2-d array
static void Preprocess()
{
arr[0][0] = 1;
for (int i = 1; i <= 1000; ++i)
{
arr[i][0] = 1;
for (int j = 1; j < i; ++j)
{
arr[i][j] = (arr[i - 1][j - 1] + arr[i - 1][j]) % mod;
}
arr[i][i] = 1;
}
}
// Function to return a raised to the power n
// with complexity O(log(n))
static long powmod(long a, long n)
{
if (n == 0)
{
return 1;
}
long pt = powmod(a, n / 2);
pt = (pt * pt) % mod;
if (n % 2 == 1)
{
return (pt * a) % mod;
}
else
{
return pt;
}
}
// Function to return the number of sub-sets
// whose median is also present in the set
static long CountSubset(int[] val, int n)
{
// Number of odd length sub-sets
long ans = powmod(2, n - 1);
// Sort the array
Arrays.sort(val);
for (int i = 0; i < n; ++i)
{
int j = i + 1;
// Checking each element for leftmost middle
// element while they are equal
while (j < n && val[j] == val[i])
{
// Calculate the number of elements in
// right of rightmost middle element
int r = n - 1 - j;
// Calculate the number of elements in
// left of leftmost middle element
int l = i;
// Add selected even length subsets
// to the answer
ans = (ans + arr[l + r][l]) % mod;
j++;
}
}
return ans;
}
// Driver code
public static void main(String[] args)
{
Preprocess();
int val[] = {2, 3, 2};
int n = val.length;
System.out.println(CountSubset(val, n));
}
}
// This code contributed by Rajput-Ji
Python3
# Python3 implementation of the approach mod = 1000000007 arr = [[None for i in range(1001)] for j in range(1001)] # Function to store pascal triangle in 2-d array def Preprocess(): arr[0][0] = 1 for i in range(1, 1001): arr[i][0] = 1 for j in range(1, i): arr[i][j] = (arr[i - 1][j - 1] + arr[i - 1][j]) % mod arr[i][i] = 1 # Function to return a raised to the power n # with complexity O(log(n)) def powmod(a, n): if not n: return 1 pt = powmod(a, n // 2) pt = (pt * pt) % mod if n % 2: return (pt * a) % mod else: return pt # Function to return the number of sub-sets # whose median is also present in the set def CountSubset(val, n): # Number of odd length sub-sets ans = powmod(2, n - 1) # Sort the array val.sort() for i in range(0, n): j = i + 1 # Checking each element for leftmost middle # element while they are equal while j < n and val[j] == val[i]: # Calculate the number of elements in # right of rightmost middle element r = n - 1 - j # Calculate the number of elements in # left of leftmost middle element l = i # Add selected even length # subsets to the answer ans = (ans + arr[l + r][l]) % mod j += 1 return ans # Driver code if __name__ == "__main__": Preprocess() val = [2, 3, 2] n = len(val) print(CountSubset(val, n)) # This code is contributed by Rituraj Jain
C#
// C# implementation of the above approach
using System;
class GFG
{
static long mod = 1000000007;
static long [,]arr = new long[1001,1001];
// Function to store pascal triangle in 2-d array
static void Preprocess()
{
arr[0,0] = 1;
for (int i = 1; i <= 1000; ++i)
{
arr[i,0] = 1;
for (int j = 1; j < i; ++j)
{
arr[i,j] = (arr[i - 1,j - 1] + arr[i - 1,j]) % mod;
}
arr[i,i] = 1;
}
}
// Function to return a raised to the power n
// with complexity O(log(n))
static long powmod(long a, long n)
{
if (n == 0)
{
return 1;
}
long pt = powmod(a, n / 2);
pt = (pt * pt) % mod;
if (n % 2 == 1)
{
return (pt * a) % mod;
}
else
{
return pt;
}
}
// Function to return the number of sub-sets
// whose median is also present in the set
static long CountSubset(int[] val, int n)
{
// Number of odd length sub-sets
long ans = powmod(2, n - 1);
// Sort the array
Array.Sort(val);
for (int i = 0; i < n; ++i)
{
int j = i + 1;
// Checking each element for leftmost middle
// element while they are equal
while (j < n && val[j] == val[i])
{
// Calculate the number of elements in
// right of rightmost middle element
int r = n - 1 - j;
// Calculate the number of elements in
// left of leftmost middle element
int l = i;
// Add selected even length subsets
// to the answer
ans = (ans + arr[l + r,l]) % mod;
j++;
}
}
return ans;
}
// Driver code
public static void Main(String[] args)
{
Preprocess();
int []val = {2, 3, 2};
int n = val.Length;
Console.WriteLine(CountSubset(val, n));
}
}
/* This code contributed by PrinciRaj1992 */
Javascript
<script>
// Js implementation of the approach
let mod = 1000000007;
let arr = [];
for(let i = 0;i<1001;i++){
arr[i] = [];
for(let j = 0;j<1001;j++){
arr[i][j] = 0;
}
}
// Function to store pascal triangle in 2-d array
function Preprocess()
{
arr[0][0] = 1;
for (let i = 1; i <= 1000; ++i) {
arr[i][0] = 1;
for (let j = 1; j < i; ++j) {
arr[i][j] = (arr[i - 1][j - 1] + arr[i - 1][j]) % mod;
}
arr[i][i] = 1;
}
}
// Function to return a raised to the power n
// with complexity O(log(n))
function powmod( a, n)
{
if (!n)
return 1;
let pt = powmod(a, Math.floor(n / 2));
pt = (pt * pt) % mod;
if (n % 2)
return (pt * a) % mod;
else
return pt;
}
// Function to return the number of sub-sets
// whose median is also present in the set
function CountSubset( val, n)
{
// Number of odd length sub-sets
let ans = powmod(2, n - 1);
// Sort the array
val.sort(function(a,b){return a-b});
for (let i = 0; i < n; ++i) {
let j = i + 1;
// Checking each element for leftmost middle
// element while they are equal
while (j < n && val[j] == val[i]) {
// Calculate the number of elements in
// right of rightmost middle element
let r = n - 1 - j;
// Calculate the number of elements in
// left of leftmost middle element
let l = i;
// Add selected even length subsets
// to the answer
ans = (ans + arr[l + r][l]) % mod;
j++;
}
}
return ans;
}
// Driver code
Preprocess();
let val = [ 2, 3, 2 ];
let n =val.length;
document.write( CountSubset(val, n),'<br>');
</script>
Producción:
5
Complejidad de tiempo: O(N 2 ), ya que estamos usando bucles anidados para atravesar N*N veces, donde N es el número de elementos en la array.
Complejidad auxiliar: O (1001 * 1001), ya que estamos usando espacio adicional para la array arr.
Publicación traducida automáticamente
Artículo escrito por sharadgoyal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA