Between Two Sets

Overview

In this article we will try to solve one of the problem mentioned in Hacker Rank. The name of the problem is Between Two Sets.

There will be two arrays of integers. Determine all integers that satisfy the following two conditions:

  • The elements of the first array are all factors of the integer being considered
  • The integer being considered is a factor of all elements of the second array.

These numbers are referred to as being between the two arrays. Determine how many such numbers exist.

Example:

a = [2,6]
b = [24,36]
There are two numbers between the arrays - 6 and 12
6%2 = 0 and 6%6 = 0 12%6 = 0 and 36%6 = 0
12%2 = 0 and 12%6 = 0 12%12 = 0 and 36%12 = 0

Code

First let us sort the two arrays:

Collections.sort(a);
Collections.sort(b);

Now let us declare some variables which we will be using in out program:

int count = 0;
int nextMultiple = 2;
int num = a.get(a.size() - 1);

count is the count of the numbers which satisfy the above mentioned conditions. nextMultiple is the factor by which we will multiple our current test value to find the next one. This will be more clear when you read the full code. num is out starting number. Since we have sorted the arrays we will start with the last number of the array a as that will be the largest number.

Now we will iterate from the last number of the array a to the first in array b:

while (num <= b.get(0)) {
  ....
}

We will check whether all the numbers in the array are a factor of num, if any one is not then we skip that number:

boolean check = true;
for (int aNum : a) {
    if (num % aNum != 0) {
        check = false;
        break;
    }
}

If all the numbers are the multiple then the value of check will be true. If that is the case them we perform the similar operation on the numbers of the array b to check if they are multiples of num.

if (check) {
    for (int bNum : b) {
        if (bNum % num != 0) {
            check = false;
            break;
        }
    }
}

If they are then check will be true. We will then increment the value of count and will calculate the next number.

BetweenTwoSets.java

import java.util.Collections;
import java.util.List;

public class BetweenTwoSets {

    public static int getTotalX(List<Integer> a, List<Integer> b) {
        Collections.sort(a);
        Collections.sort(b);
        int count = 0;
        int nextMultiple = 2;
        int num = a.get(a.size() - 1);
        while (num <= b.get(0)) {
            boolean check = true;
            for (int aNum : a) {
                if (num % aNum != 0) {
                    check = false;
                    break;
                }
            }
            if (check) {
                for (int bNum : b) {
                    if (bNum % num != 0) {
                        check = false;
                        break;
                    }
                }
            }
            if (check) {
                count++;
            }
            num = a.get(a.size() - 1) * nextMultiple;
            nextMultiple++;
        }
        return count;
    }
}

Test

Below is the simple JUnit test for the above code:

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

import static org.junit.Assert.*;

public class BetweenTwoSetsTest {

    @Test
    public void getTotalX() {
        List<Integer> a = new ArrayList(); a.add(2); a.add(4);
        List<Integer> b = new ArrayList(); b.add(16); b.add(32); b.add(96);
        assertEquals(3, BetweenTwoSets.getTotalX(a, b));
    }
}

Conclusion

In this article we discussed how to solve the Between Two Sets problem in Java.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: