Count number of subsets of a set with GCD equal to a given number - GeeksforGeeks

Count number of subsets of a set with GCD equal to a given number - GeeksforGeeks

Given a set of positive integer elements, find count of subsets with GCDs equal to given numbers.

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}  

A Simple Solution is to generate all subsets of given set and find GCD of every subset.

Below is an Efficient Solution for small numbers, i,e, the maximum of all numbers is not very high.

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. 

How does step 3.a work?
How to get number of subsets for a given GCD ‘i’ where i lies in range from 1 to arrMax. The idea is to count all multiples of i using ‘freq’ built in step 2. Let there be ‘add’ multiples of i. The number of all possible subsets with ‘add’ numbers would be “pow(2, add) – 1″, excluding the empty set. For example, if given array is {2, 3, 6} and i = 3, there are 2 multiples of 3 (3 and 6). So there will be 3 subsets {3}, {3, 6} and {6} which have a multiple of i as GCD. These subsets also include {6} which doesn’t have 3 as GCD, but a multiple of 3. So we need to subtract such subsets. We store subset counts for every GCD in another hash map ‘subset’. Let ‘sub’ be the number of subsets which have multiple of ‘i’ as GCD. The value of ‘sub’ for any multiple of ‘i’ can directly be obtained from subset[] as we are evaluating counts from arrMax to 1.

void ccountSubsets(int arr[], int n, int gcd[], int m)

{

    // Map to store frequency of array elements

    map<int, int> freq;

 

    // Map to store number of subsets with given gcd

    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} cnsidering i = 2 and

            // subset we need to exclude are those havng 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;

}

Exercise: Extend the above solution so that all calculations are done under modulo 1000000007 to avoid overflows.

Read full article from Count number of subsets of a set with GCD equal to a given number - GeeksforGeeks