CODEWITHSUNDEEP
javaalgorithmset
Err Or
Err Or

Reputation: 13

Calculate set of pair by taking one value from each set

I'm tring to calculate possible number of pair, that can be made by taking value from both two set. No one set repitation. I'm also trying to implement it using Java Set. But I'm stuck at logic, How to count such possible combination.

Problem example:

Input:
Set 1: [0, 1, 4]
Set 2: [2, 3]
Set None: []

Here, Possible pair combination are [0,2] , [0,3] , [1,2] , [1,3] , [4,2] , [4,3] 

Output:
6 combination to choose pair by taking one value from each set

Here is Code:

static Set<Integer> countryOne = new HashSet();
static Set<Integer> countryTwo = new HashSet();
static Set<Integer> countryNone = new HashSet();

static int journeyToMoon(int n, int[][] astronaut) {
    ///Separating diffrent country from input
    countryOne.add(astronaut[0][0]); countryOne.add(astronaut[0][1]);
    for(int i=1; i<astronaut.length; i++){
        boolean countryCheckFlag = false;
        for(int j=0; j<astronaut[i].length; j++){
            if(countryOne.contains(astronaut[i][j])){
                countryCheckFlag = true;
            }
        }
        if(countryCheckFlag){countryOne.add(astronaut[i][0]); countryOne.add(astronaut[i][1]);}
        else {countryTwo.add(astronaut[i][0]); countryTwo.add(astronaut[i][1]);}
    }

    ///Separating country which not present in input
    for(int i=0; i<n; i++){
        if(!countryOne.contains(i) && !countryTwo.contains(i))
            countryNone.add(i);
    }

    //Now i have two diffrent set

    return 0;
}

Input might be diffrent at a certain level, like this

Input:
Set 1: [0, 2]
Set 2: []
Set None: [1, 3]

Here, Possible pair combination are [0,1] , [0,3] , [2,1] , [2,3] as like before, But as it is it Set None, so it will create set between Set None as extra, like [1,3]

Output:
5 combination to choose pair by taking one value from each set

Here Might be Answer like, Total combination = (Possible combination of set one and set two with product) + (Possible combination of set 1 and set 2 with set none each) + (All possible combination of Set None with diffrent value)

If so, How to calculate it. Input range will be between 1 to 10^5. Thanks.

Upvotes: 1

Views: 87

Answers (1)

Antimon
Antimon

Reputation: 231

To calculate the total number of combinations you can simply use

int a = set1.size() * set2.size();

To calculate the total number of pairs of n elements you can use the formula (n*n - n) / 2, so in your example this might be

int x = setNone.size();
int b = (x * x - x) / 2

Upvotes: 1

Related Questions