Regla de la suma: si una tarea se puede realizar de una de n 1 formas o una de n 2 formas, donde ninguna del conjunto de n 1 formas es igual a cualquiera del conjunto de n 2 formas, entonces hay n 1 + n 2 maneras de hacer la tarea. La regla de la suma mencionada anteriormente establece que si hay varios conjuntos de formas de realizar una tarea, no debería haber ninguna forma común entre dos conjuntos de formas porque, si la hay, se contaría dos veces y la enumeración sería equivocado.
El principio de inclusión-exclusión dice que para contar solo formas únicas de hacer una tarea, debemos sumar la cantidad de formas de hacerla de una forma y la cantidad de formas de hacerla de otra y luego restar la cantidad de formas. para hacer la tarea que son comunes a ambos conjuntos de formas.
El principio de inclusión-exclusión también se conoce como principio de sustracción . Para dos conjuntos de formas A i y A 2 , la enumeración sería-
| UN 1 ∪ UN 2 |= | UN 1 |+ | un 2 | – |A 1 ∩ A 2 |
A continuación se presentan algunos ejemplos para explicar la aplicación del principio de inclusión-exclusión:
Ejemplo 1: ¿Cuántas strings binarias de longitud 8 comienzan con un bit ‘1’ o terminan con dos bits ’00’?
Solución: si la string comienza con uno, quedan 7 caracteres que se pueden completar de 2 7 = 128 formas.
Si la string termina con ’00’, se pueden completar 6 caracteres de 2 6 = 64 formas.
Ahora bien, si sumamos los conjuntos de formas anteriores y concluimos que es la respuesta final, entonces sería incorrecto. Esto se debe a que hay strings que comienzan con ‘1’ y terminan con ’00’, y dado que cumplen ambos criterios, se cuentan dos veces.
Entonces necesitamos restar tales strings para obtener un conteo correcto.
Las strings que comienzan con ‘1’ y terminan con ’00’ tienen cinco caracteres que se pueden completar de 2 5 = 32 formas.
Por el principio de inclusión-exclusión obtenemos: Total de strings = 128 + 64 – 32 = 160
Ejemplo 2: ¿Cuántos números entre 1 y 1000, incluidos ambos, son divisibles por 3 o por 4?
Solución: Número de números divisibles por 3 =
= 
. Número de números divisibles por 4 = 
= 
.Número de números divisibles por 3 y 4 = 
= 
Por lo tanto, número de números divisible por 3 o 4 = 
= 333 + 250 – 83 = 500
Implementación
Problema 1: ¿Cuántos números entre 1 y 1000, incluidos ambos, son divisibles por 3 o por 4?
El Enfoque será el discutido anteriormente, sumamos el número de números que son divisibles por 3 y 4 y restamos los números que son divisibles por 12.
C++
// CPP program to count the
// number of numbers between
// 1 and 1000, including both,
// that are divisible by 3 or 4
#include <bits/stdc++.h>
using namespace std;
// function to count the divisors
int countDivisors(int N, int a, int b)
{
// Counts of numbers
// divisible by a and b
int count1 = N / a;
int count2 = N / b;
// inclusion-exclusion
// principle applied
int count3 = (N / (a * b));
return count1 + count2 - count3;
}
// Driver Code
int main()
{
int N = 1000, a = 3, b = 4;
cout << countDivisors(N, a, b);
return 0;
}
Java
// Java program to count the
// number of numbers between
// 1 and 1000, including both,
// that are divisible by 3 or 4
import java.io.*;
class GFG {
// function to count the divisors
public static int countDivisors(int N, int a, int b)
{
// Counts of numbers
// divisible by a and b
int count1 = N / a;
int count2 = N / b;
// inclusion-exclusion
// principle applied
int count3 = (N / (a * b));
return count1 + count2 - count3;
}
// Driver Code
public static void main(String[] args)
{
int N = 1000, a = 3, b = 4;
System.out.println(countDivisors(N, a, b));
}
}
// This code is contributed by m_kit
Python3
# Python3 program to count the # number of numbers between # 1 and 1000, including both, # that are divisible by 3 or 4 # function to count the divisors def countDivisors(N, a, b): # Counts of numbers # divisible by a and b count1 = N // a count2 = N // b # inclusion-exclusion # principle applied count3 = (N // (a * b)) return count1 + count2 - count3 # Driver Code N = 1000 a = 3 b = 4 print(countDivisors(N, a, b)) # This code is contributed by shubhamsingh10
C#
// C# program to count the
// number of numbers between
// 1 and 1000, including both,
// that are divisible by 3 or 4
using System;
class GFG {
// function to count
// the divisors
public static int countDivisors(int N, int a, int b)
{
// Counts of numbers
// divisible by a and b
int count1 = N / a;
int count2 = N / b;
// inclusion-exclusion
// principle applied
int count3 = (N / (a * b));
return count1 + count2 - count3;
}
// Driver Code
static public void Main()
{
int N = 1000, a = 3, b = 4;
Console.WriteLine(countDivisors(N, a, b));
}
}
// This code is contributed by aj_36
PHP
<?php
// PHP program to count the
// number of numbers between
// 1 and 1000, including both,
// that are divisible by 3 or 4
// function to count the divisors
function countDivisors($N, $a, $b)
{
// Counts of numbers
// divisible by a and b
$count1 = $N / $a;
$count2 = $N / $b;
// inclusion-exclusion
// principle applied
$count3 = ($N / ($a * $b));
return $count1 + $count2 - $count3;
}
// Driver Code
$N = 1000; $a = 3; $b = 4;
echo countDivisors($N, $a, $b);
// This code is contributed by aj_36
?>
Javascript
<script>
// Javascript program to count the
// number of numbers between
// 1 and 1000, including both,
// that are divisible by 3 or 4
// function to count
// the divisors
function countDivisors(N, a, b)
{
// Counts of numbers
// divisible by a and b
let count1 = parseInt(N / a, 10);
let count2 = parseInt(N / b, 10);
// inclusion-exclusion
// principle applied
let count3 = parseInt(N / (a * b), 10);
return count1 + count2 - count3;
}
let N = 1000, a = 3, b = 4;
document.write(countDivisors(N, a, b));
</script>
Producción :
500
Problema 2: Dados N números primos y un número M, averiguar cuántos números del 1 al M son divisibles por cualquiera de los N números primos dados.
Ejemplos:
Input: N numbers = {2, 3, 5, 7} M = 100
Output: 78
Input: N numbers = {2, 5, 7, 11} M = 200
Output: 137
El enfoque para este problema será generar todas las combinaciones posibles de números usando N números primos usando el conjunto de potencias en 2 N . Para cada uno de los números primos dados P i entre N, tiene M/P i múltiplos . Supongamos que M=10, y tenemos 3 números primos (2, 3, 5), entonces la cuenta total de múltiplos cuando hacemos 10/2 + 10/3 + 10/5 es 11. Ya que estamos contando 6 y 10 dos veces, el conteo de múltiplos en el rango 1-M es 11. Usando el principio de inclusión-exclusión , podemos obtener el número correcto de múltiplos. El principio de inclusión-exclusión para tres términos se puede describir como:
De manera similar, para cada N números, podemos encontrar fácilmente el número total de múltiplos en el rango de 1 a M aplicando la fórmula para una intersección de N números. Los números que se forman por la multiplicación de un número impar de números primos se sumarán y los números formados por la multiplicación de números pares se restarán para obtener el número total de múltiplos en el rango de 1 a M.
Usando power set podemos obtener fácilmente todas las combinaciones de números formadas por los números primos dados. Para saber si el número está formado por la multiplicación de números pares o impares, basta con contar el número de bits establecidos en todas las combinaciones posibles (1-1<<N) .
Usando conjuntos de potencia y sumando los números creados por combinaciones de números primos pares e impares, obtenemos 123 y 45 respectivamente. Usando el principio de inclusión-exclusión obtenemos el número de números en el rango 1-M que se divide por cualquiera de N números primos (combinaciones impares-combinaciones pares) = (123-45) = 78.
A continuación se muestra la implementación de la idea anterior:
C++
// CPP program to count the
// number of numbers in range
// 1-M that are divisible by
// given N prime numbers
#include <bits/stdc++.h>
using namespace std;
// function to count the number
// of numbers in range 1-M that
// are divisible by given N
// prime numbers
int count(int a[], int m, int n)
{
int odd = 0, even = 0;
int counter, i, j, p = 1;
int pow_set_size = (1 << n);
// Run from counter 000..0 to 111..1
for (counter = 1; counter < pow_set_size; counter++) {
p = 1;
for (j = 0; j < n; j++) {
// Check if jth bit in the
// counter is set If set
// then print jth element from set
if (counter & (1 << j)) {
p *= a[j];
}
}
// if set bits is odd, then add to
// the number of multiples
if (__builtin_popcount(counter) & 1)
odd += (m / p);
else
even += (m / p);
}
return odd - even;
}
// Driver Code
int main()
{
int a[] = { 2, 3, 5, 7 };
int m = 100;
int n = sizeof(a) / sizeof(a[0]);
cout << count(a, m, n);
return 0;
}
Java
// Java program to count the
// number of numbers in range
// 1-M that are divisible by
// given N prime numbers
import java.io.*;
class GFG {
// function to count the number
// of numbers in range 1-M that
// are divisible by given N
// prime numbers
public static int count(int a[], int m, int n)
{
int odd = 0;
int even = 0;
int counter = 0;
int i = 0;
int j = 0;
int p = 1;
int pow_set_size = (1 << n);
// Run from counter 000..0 to 111..1
for (counter = 1; counter < pow_set_size;
counter++) {
p = 1;
for (j = 0; j < n; j++) {
// Check if jth bit in the
// counter is set If set
// then print jth element from set
if ((counter & (1 << j)) > 0) {
p *= a[j];
}
}
// if set bits is odd, then add to
// the number of multiples
if (Integer.bitCount(counter) % 2 == 1) {
odd += (m / p);
}
else {
even += (m / p);
}
}
return odd - even;
}
// Driver Code
public static void main(String[] args)
{
int a[] = { 2, 3, 5, 7 };
int m = 100;
int n = a.length;
System.out.println(count(a, m, n));
}
}
Python3
# Python3 program to count the
# number of numbers in range
# 1-M that are divisible by
# given N prime numbers
def bitsoncount(x):
return bin(x).count('1')
# function to count the number
# of numbers in range 1-M that
# are divisible by given N
# prime numbers
def count(a, m, n):
odd = 0
even = 0
p = 1
pow_set_size = 1 << n
# Run from counter 000..0 to 111..1
for counter in range(1, pow_set_size):
p = 1
for j in range(n):
# Check if jth bit in the
# counter is set If set
# then print jth element from set
if (counter & (1 << j)):
p *= a[j]
# if set bits is odd, then add to
# the number of multiples
if (bitsoncount(counter) & 1):
odd += (m // p)
else:
even += (m // p)
return odd - even
# Driver Code
a = [2, 3, 5, 7]
m = 100
n = len(a)
print(count(a, m, n))
# This code is contributed by shivanisinghss2110
Javascript
<script>
// Javascript program to count the
// number of numbers in range
// 1-M that are divisible by
// given N prime numbers
// Bit count
function bitCount(n)
{
n = n - ((n >> 1) & 0x55555555)
n = (n & 0x33333333) +
((n >> 2) & 0x33333333)
return ((n + (n >> 4) & 0xF0F0F0F) *
0x1010101) >> 24
}
// Function to count the number
// of numbers in range 1-M that
// are divisible by given N
// prime numbers
function count(a, m, n)
{
var odd = 0;
var even = 0;
var counter = 0;
var i = 0;
var j = 0;
var p = 1;
var pow_set_size = (1 << n);
// Run from counter 000..0 to 111..1
for(counter = 1;
counter < pow_set_size;
counter++)
{
p = 1;
for(j = 0; j < n; j++)
{
// Check if jth bit in the
// counter is set If set
// then print jth element from set
if ((counter & (1 << j)) > 0)
{
p *= a[j];
}
}
// If set bits is odd, then add to
// the number of multiples
if (bitCount(counter) % 2 == 1)
{
odd += parseInt(m / p);
}
else
{
even += parseInt(m / p);
}
}
return odd - even;
}
// Driver Code
var a = [ 2, 3, 5, 7 ];
var m = 100;
var n = a.length;
document.write(count(a, m, n));
// This code is contributed by Rajput-Ji
</script>
Producción:
78
Complejidad del tiempo: O(2 N *N)