Dado un conjunto de elementos enteros positivos, encuentre el recuento de subconjuntos con GCD iguales a los números dados.
Ejemplos:
Input: arr[] = {2, 3, 4}, gcd[] = {2, 3}
Output: Number of subsets with gcd 2 is 2
Number of subsets with gcd 3 is 1
The two subsets with GCD equal to 2 are {2} and {2, 4}.
The one subset with GCD equal to 3 ss {3}.
Input: arr[] = {6, 3, 9, 2}, gcd = {3, 2}
Output: Number of subsets with gcd 3 is 5
Number of subsets with gcd 2 is 2
The five subsets with GCD equal to 3 are {3}, {6, 3},
{3, 9}, {6, 9) and {6, 3, 9}.
The two subsets with GCD equal to 2 are {2} and {2, 6}
Le recomendamos encarecidamente que minimice su navegador y que pruebe esto usted mismo primero.
Una solución simple es generar todos los subconjuntos de un conjunto dado y encontrar el GCD de cada subconjunto.
A continuación se muestra una solución eficiente para números pequeños, es decir, el máximo de todos los números no es muy alto.
1) Find the maximum number of given numbers. Let the
maximum be arrMax.
2) Count occurrences of all numbers using a hash. Let
this hash be 'freq'
3) The maximum possible GCD can be arrMax. Run a loop
for i = arrMax to 1
a) Count number of subsets for current GCD.
4) Now we have counts for all possible GCDs, return
count for given gcds.
¿Cómo funciona el paso 3.a?
Cómo obtener el número de subconjuntos para un GCD ‘i’ dado donde i se encuentra en el rango de 1 a arrMax. La idea es contar todos los múltiplos de i usando el paso 2 incorporado ‘freq’. Que haya ‘agregar’ múltiplos de i. El número de todos los subconjuntos posibles con números ‘sumar’ sería “pow(2, suma) – 1”, excluyendo el conjunto vacío. Por ejemplo, si la array dada es {2, 3, 6} e i = 3, hay 2 múltiplos de 3 (3 y 6). Entonces habrá 3 subconjuntos {3}, {3, 6} y {6} que tienen un múltiplo de i como MCD. Estos subconjuntos también incluyen {6} que no tiene 3 como MCD, sino un múltiplo de 3. Por lo tanto, debemos restar dichos subconjuntos. Almacenamos recuentos de subconjuntos para cada GCD en otro ‘subconjunto’ de mapa hash. Sea ‘sub’ el número de subconjuntos que tienen un múltiplo de ‘i’ como GCD.
A continuación se muestra la implementación de la idea anterior.
C++
// C++ program to count number of subsets with given GCDs
#include<bits/stdc++.h>
using namespace std;
// n is size of arr[] and m is sizeof gcd[]
void ccountSubsets(int arr[], int n, int gcd[], int m)
{
// Map to store frequency of array elements
unordered_map<int, int> freq;
// Map to store number of subsets with given gcd
unordered_map<int, int> subsets;
// Initialize maximum element. Assumption: all array
// elements are positive.
int arrMax = 0;
// Find maximum element in array and fill frequency
// map.
for (int i=0; i<n; i++)
{
arrMax = max(arrMax, arr[i]);
freq[arr[i]]++;
}
// Run a loop from max element to 1 to find subsets
// with all gcds
for (int i=arrMax; i>=1; i--)
{
int sub = 0;
int add = freq[i];
// Run a loop for all multiples of i
for (int j = 2; j*i <= arrMax; j++)
{
// Sum the frequencies of every element which
// is a multiple of i
add += freq[j*i];
// Excluding those subsets which have gcd > i but
// not i i.e. which have gcd as multiple of i in
// the subset for ex: {2,3,4} considering i = 2 and
// subset we need to exclude are those having gcd as 4
sub += subsets[j*i];
}
// Number of subsets with GCD equal to 'i' is pow(2, add)
// - 1 - sub
subsets[i] = (1<<add) - 1 - sub;
}
for (int i=0; i<m; i++)
cout << "Number of subsets with gcd " << gcd[i] << " is "
<< subsets[gcd[i]] << endl;
}
// Driver program
int main()
{
int gcd[] = {2, 3};
int arr[] = {9, 6, 2};
int n = sizeof(arr)/sizeof(arr[0]);
int m = sizeof(gcd)/sizeof(gcd[0]);
ccountSubsets(arr, n, gcd, m);
return 0;
}
Java
// Java program to count
// number of subsets with
// given GCDs
import java.util.*;
class GFG{
// n is size of arr[] and
// m is sizeof gcd[]
static void ccountSubsets(int arr[], int n,
int gcd[], int m)
{
// Map to store frequency
// of array elements
HashMap<Integer,
Integer> freq =
new HashMap<Integer,
Integer>();
// Map to store number of
// subsets with given gcd
HashMap<Integer,
Integer> subsets =
new HashMap<Integer,
Integer>();
// Initialize maximum element.
// Assumption: all array
// elements are positive.
int arrMax = 0;
// Find maximum element in
// array and fill frequency
// map.
for (int i = 0; i < n; i++)
{
arrMax = Math.max(arrMax,
arr[i]);
if(freq.containsKey(arr[i]))
{
freq.put(arr[i],
freq.get(arr[i]) + 1);
}
else
{
freq.put(arr[i], 1);
}
}
// Run a loop from max element
// to 1 to find subsets
// with all gcds
for (int i = arrMax; i >= 1; i--)
{
int sub = 0;
int add = 0;
if(freq.containsKey(i))
add = freq.get(i);
// Run a loop for all multiples
// of i
for (int j = 2; j * i <= arrMax; j++)
{
// Sum the frequencies of
// every element which
// is a multiple of i
if(freq.containsKey(i * j))
add += freq.get(j * i);
// Excluding those subsets
// which have gcd > i but
// not i i.e. which have
// gcd as multiple of i in
// the subset for ex: {2,3,4}
// considering i = 2 and
// subset we need to exclude
// are those having gcd as 4
sub += subsets.get(j * i);
}
// Number of subsets with GCD
// equal to 'i' is Math.pow(2, add)
// - 1 - sub
subsets.put(i, (1 << add) -
1 - sub);
}
for (int i = 0; i < m; i++)
System.out.print("Number of subsets with gcd " +
gcd[i] + " is " +
subsets.get(gcd[i]) + "\n");
}
// Driver program
public static void main(String[] args)
{
int gcd[] = {2, 3};
int arr[] = {9, 6, 2};
int n = arr.length;
int m = gcd.length;
ccountSubsets(arr, n, gcd, m);
}
}
// This code is contributed by shikhasingrajput
Python3
# Python3 program to count number of
# subsets with given GCDs
# n is size of arr[] and m is sizeof gcd[]
def countSubsets(arr, n, gcd, m):
# Map to store frequency of array elements
freq = dict()
# Map to store number of subsets
# with given gcd
subsets = dict()
# Initialize maximum element.
# Assumption: all array elements
# are positive.
arrMax = 0
# Find maximum element in array and
# fill frequency map.
for i in range(n):
arrMax = max(arrMax, arr[i])
if arr[i] not in freq:
freq[arr[i]] = 1
else:
freq[arr[i]] += 1
# Run a loop from max element to 1
# to find subsets with all gcds
for i in range(arrMax, 0, -1):
sub = 0
add = 0
if i in freq:
add = freq[i]
j = 2
# Run a loop for all multiples of i
while j * i <= arrMax:
# Sum the frequencies of every element
# which is a multiple of i
if j * i in freq:
add += freq[j * i]
# Excluding those subsets which have
# gcd > i but not i i.e. which have gcd
# as multiple of i in the subset.
# for ex: {2,3,4} considering i = 2 and
# subset we need to exclude are those
# having gcd as 4
sub += subsets[j * i]
j += 1
# Number of subsets with GCD equal
# to 'i' is pow(2, add) - 1 - sub
subsets[i] = (1 << add) - 1 - sub
for i in range(m):
print("Number of subsets with gcd %d is %d" %
(gcd[i], subsets[gcd[i]]))
# Driver Code
if __name__ == "__main__":
gcd = [2, 3]
arr = [9, 6, 2]
n = len(arr)
m = len(gcd)
countSubsets(arr, n, gcd, m)
# This code is contributed by
# sanjeev2552
C#
// C# program to count
// number of subsets with
// given GCDs
using System;
using System.Collections.Generic;
class GFG{
// n is size of []arr and
// m is sizeof gcd[]
static void ccountSubsets(int []arr, int n,
int []gcd, int m)
{
// Map to store frequency
// of array elements
Dictionary<int,
int> freq =
new Dictionary<int,
int>();
// Map to store number of
// subsets with given gcd
Dictionary<int,
int> subsets =
new Dictionary<int,
int>();
// Initialize maximum element.
// Assumption: all array
// elements are positive.
int arrMax = 0;
// Find maximum element in
// array and fill frequency
// map.
for (int i = 0; i < n; i++)
{
arrMax = Math.Max(arrMax,
arr[i]);
if(freq.ContainsKey(arr[i]))
{
freq.Add(arr[i],
freq[arr[i]] + 1);
}
else
{
freq.Add(arr[i], 1);
}
}
// Run a loop from max element
// to 1 to find subsets
// with all gcds
for (int i = arrMax; i >= 1; i--)
{
int sub = 0;
int add = 0;
if(freq.ContainsKey(i))
add = freq[i];
// Run a loop for all
// multiples of i
for (int j = 2;
j * i <= arrMax; j++)
{
// Sum the frequencies of
// every element which
// is a multiple of i
if(freq.ContainsKey(i * j))
add += freq[j * i];
// Excluding those subsets
// which have gcd > i but
// not i i.e. which have
// gcd as multiple of i in
// the subset for ex: {2,3,4}
// considering i = 2 and
// subset we need to exclude
// are those having gcd as 4
sub += subsets[j * i];
}
// Number of subsets with GCD
// equal to 'i' is Math.Pow(2, add)
// - 1 - sub
subsets.Add(i, (1 << add) -
1 - sub);
}
for (int i = 0; i < m; i++)
Console.Write("Number of subsets with gcd " +
gcd[i] + " is " +
subsets[gcd[i]] + "\n");
}
// Driver code
public static void Main(String[] args)
{
int []gcd = {2, 3};
int []arr = {9, 6, 2};
int n = arr.Length;
int m = gcd.Length;
ccountSubsets(arr, n, gcd, m);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript program to count number of
// subsets with given GCDs
// n is size of arr[] and m is sizeof gcd[]
function countSubsets(arr, n, gcd, m){
// Map to store frequency of array elements
let freq = new Map
// Map to store number of subsets
// with given gcd
let subsets = new Map
// Initialize maximum element.
// Assumption: all array elements
// are positive.
let arrMax = 0
// Find maximum element in array and
// fill frequency map.
for(let i = 0; i < n; i++)
{
arrMax = Math.max(arrMax, arr[i])
if(freq.has(arr[i]) == false)
freq.set(arr[i], 1)
else
freq.set(arr[i], freq.get(arr[i])+1)
}
// Run a loop from max element to 1
// to find subsets with all gcds
for(let i = arrMax; i > 0; i--)
{
let sub = 0
let add = 0
if(freq.has(i))
add = freq.get(i)
let j = 2
// Run a loop for all multiples of i
while(j * i <= arrMax){
// Sum the frequencies of every element
// which is a multiple of i
if(freq.has(j * i))
add += freq.get(j * i)
// Excluding those subsets which have
// gcd > i but not i i.e. which have gcd
// as multiple of i in the subset.
// for ex: {2,3,4} considering i = 2 and
// subset we need to exclude are those
// having gcd as 4
sub += subsets.get(j * i)
j += 1
}
// Number of subsets with GCD equal
// to 'i' is pow(2, add) - 1 - sub
subsets.set(i , (1 << add) - 1 - sub)
}
for(let i = 0; i < m; i++)
{
document.write( `Number of subsets with gcd ${gcd[i]} is ${subsets.get(gcd[i])}`,"</br>")
}
}
// Driver Code
let gcd = [2, 3]
let arr = [9, 6, 2]
let n = arr.length
let m = gcd.length
countSubsets(arr, n, gcd, m)
// This code is contributed by shinjanpatra
</script>
Producción:
Number of subsets with gcd 2 is 2 Number of subsets with gcd 3 is 1
Complejidad temporal: O(m 2 ) , donde m es el elemento máximo del vector.
Espacio Auxiliar: O(n)
Ejercicio: Amplíe la solución anterior para que todos los cálculos se realicen en módulo 1000000007 para evitar desbordamientos.
Este artículo es una contribución de Aarti_Rathi y Ekta Goel . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
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