Dado un número entero N , la tarea es encontrar el número de strings binarias de longitud N tal que la frecuencia de 1 sea mayor que la frecuencia de 0 .
Ejemplo:
Entrada: N = 2
Salida: 1
Explicación: El recuento de strings binarias de longitud 2 es 4, es decir, {“00”, “01”, “10”, “11”}.
La única string que tiene una frecuencia de 1 mayor que la de 0 es «11».Entrada: N = 3
Salida: 4
Explicación: El recuento de strings binarias de longitud 3 es 8, es decir, {“000”, “001”, “010”, “011”, “100”, “101”, “110”, “ 111”}.
Entre ellos, las strings que tienen una frecuencia de 1 mayor que 0 son {“011”, “101”, “110”, “111”}.
Enfoque ingenuo: el enfoque más simple para resolver este problema es generar todas las strings binarias de longitud N e iterar sobre cada string para encontrar la frecuencia de 1 y 0. Si la frecuencia de 1 es mayor que la de 0, incremente el contador. Finalmente, imprima el conteo.
Complejidad temporal: O(N*2 N )
Espacio auxiliar: O(1)
Enfoque eficiente: para observar el enfoque anterior, es necesario realizar las siguientes observaciones:
S Total = Número total de strings binarias de longitud N = 2 N
S igual = Número de strings binarias de longitud N que tienen la misma frecuencia de 0 y 1.
S 1 = Número de strings binarias de longitud N que tienen una frecuencia de 1 mayor que 0.
S 0 = Número de strings binarias de longitud N que tienen una frecuencia de 0 mayor que 1.
S total = S igual + S 1 + S 0
- Para cada string en S 1 , existe una string en S 0.
Supongamos que » 1110 » es la string en S 1 , entonces su string correspondiente en S 0 será » 0001 «. De manera similar, para cada string en S 1 existe una string en S 0 . Por lo tanto, S 1 = S 0 (para todo N ). - Si N es impar entonces S igual = 0 .
- Si N es par entonces S igual =C(N, N/2) .
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 calculate and return the value of Binomial
// Coefficient C(n, k)
unsigned long int binomialCoeff(unsigned long int n,
unsigned long int k)
{
unsigned long int res = 1;
// Since C(n, k) = C(n, n-k)
if (k > n - k)
k = n - k;
// Calculate the value of
// [n*(n-1)*---*(n-k+1)] / [k*(k-1)*---*1]
for (int i = 0; i < k; ++i) {
res *= (n - i);
res /= (i + 1);
}
return res;
}
// Function to return the count of binary strings of length
// N such that frequency of 1's exceed that of 0's
unsigned long int countOfString(int N)
{
// Count of N-length binary strings
unsigned long int Stotal = pow(2, N);
// Count of N- length binary strings having equal count
// of 0's and 1's
unsigned long int Sequal = 0;
// For even length strings
if (N % 2 == 0)
Sequal = binomialCoeff(N, N / 2);
unsigned long int S1 = (Stotal - Sequal) / 2;
return S1;
}
// Driver Code
int main()
{
int N = 3;
cout << countOfString(N);
return 0;
}
C
// C Program to implement the above approach
#include <stdio.h>
#include <math.h>
// Function to calculate and return the value of Binomial
// Coefficient C(n, k)
unsigned long int binomialCoeff(unsigned long int n,
unsigned long int k)
{
unsigned long int res = 1;
// Since C(n, k) = C(n, n-k)
if (k > n - k)
k = n - k;
// Calculate the value of
// [n*(n-1)*---*(n-k+1)] / [k*(k-1)*---*1]
for (int i = 0; i < k; ++i) {
res *= (n - i);
res /= (i + 1);
}
return res;
}
// Function to return the count of binary strings of length
// N such that frequency of 1's exceed that of 0's
unsigned long int countOfString(int N)
{
// Count of N-length binary strings
unsigned long int Stotal = pow(2, N);
// Count of N- length binary strings having equal count
// of 0's and 1's
unsigned long int Sequal = 0;
// For even length strings
if (N % 2 == 0)
Sequal = binomialCoeff(N, N / 2);
unsigned long int S1 = (Stotal - Sequal) / 2;
return S1;
}
// Driver Code
int main()
{
int N = 3;
printf("%lu", countOfString(N));
return 0;
}
// This code is contributed by Sania Kumari Gupta
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
// Function to calculate
// and return the value of
// Binomial Coefficient C(n, k)
static int binomialCoeff(int n, int k)
{
int res = 1;
// Since C(n, k) = C(n, n-k)
if (k > n - k)
k = n - k;
// Calculate the value of
// [n*(n-1)*---*(n-k+1)] / [k*(k-1)*---*1]
for(int i = 0; i < k; ++i)
{
res *= (n - i);
res /= (i + 1);
}
return res;
}
// Function to return the count of
// binary Strings of length N such
// that frequency of 1's exceed that of 0's
static int countOfString(int N)
{
// Count of N-length binary Strings
int Stotal = (int) Math.pow(2, N);
// Count of N- length binary Strings
// having equal count of 0's and 1's
int Sequal = 0;
// For even length Strings
if (N % 2 == 0)
Sequal = binomialCoeff(N, N / 2);
int S1 = (Stotal - Sequal) / 2;
return S1;
}
// Driver Code
public static void main(String[] args)
{
int N = 3;
System.out.print(countOfString(N));
}
}
// This code is contributed by Amit Katiyar
Python3
# Python3 program to implement # the above approach # Function to calculate # and return the value of # Binomial Coefficient C(n, k) def binomialCoeff(n, k): res = 1 # Since C(n, k) = C(n, n-k) if(k > n - k): k = n - k # Calculate the value of # [n*(n-1)*---*(n-k+1)] / [k*(k-1)*---*1] for i in range(k): res *= (n - i) res //= (i + 1) return res # Function to return the count of # binary strings of length N such # that frequency of 1's exceed that of 0's def countOfString(N): # Count of N-length binary strings Stotal = pow(2, N) # Count of N- length binary strings # having equal count of 0's and 1's Sequal = 0 # For even length strings if(N % 2 == 0): Sequal = binomialCoeff(N, N // 2) S1 = (Stotal - Sequal) // 2 return S1 # Driver Code N = 3 print(countOfString(N)) # This code is contributed by Shivam Singh
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Function to calculate
// and return the value of
// Binomial Coefficient C(n, k)
static int binomialCoeff(int n, int k)
{
int res = 1;
// Since C(n, k) = C(n, n-k)
if (k > n - k)
k = n - k;
// Calculate the value of
// [n*(n-1)*---*(n-k+1)] / [k*(k-1)*---*1]
for(int i = 0; i < k; ++i)
{
res *= (n - i);
res /= (i + 1);
}
return res;
}
// Function to return the count of
// binary Strings of length N such
// that frequency of 1's exceed that of 0's
static int countOfString(int N)
{
// Count of N-length binary Strings
int Stotal = (int) Math.Pow(2, N);
// Count of N- length binary Strings
// having equal count of 0's and 1's
int Sequal = 0;
// For even length Strings
if (N % 2 == 0)
Sequal = binomialCoeff(N, N / 2);
int S1 = (Stotal - Sequal) / 2;
return S1;
}
// Driver Code
public static void Main(String[] args)
{
int N = 3;
Console.Write(countOfString(N));
}
}
// This code is contributed by sapnasingh4991
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to calculate
// and return the value of
// Binomial Coefficient C(n, k)
function binomialCoeff(n, k)
{
let res = 1;
// Since C(n, k) = C(n, n-k)
if (k > n - k)
k = n - k;
// Calculate the value of
// [n*(n-1)*---*(n-k+1)] / [k*(k-1)*---*1]
for(let i = 0; i < k; ++i)
{
res *= (n - i);
res /= (i + 1);
}
return res;
}
// Function to return the count of
// binary Strings of length N such
// that frequency of 1's exceed that of 0's
function countOfString(N)
{
// Count of N-length binary Strings
let Stotal = Math.pow(2, N);
// Count of N- length binary Strings
// having equal count of 0's and 1's
let Sequal = 0;
// For even length Strings
if (N % 2 == 0)
Sequal = binomialCoeff(N, N / 2);
let S1 = (Stotal - Sequal) / 2;
return S1;
}
let N = 3;
document.write(countOfString(N));
// This code is contributed by divyeshrabadiya07.
</script>
4
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por math_lover y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA