Between Two Sets Hackerrank solution in Java with explanation

Java solution for Between Two Sets HackerRank Problem

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

1. The elements of the first array are all factors of the integer being considered
2. 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.

So we have to all common numbers that are 

1. Multiple of first array and  
2. Factors of second array
   

Example 1 :

a = [2, 6]

b = [24, 36]

There are two numbers between the arrays : 6, 12. So answer is 2. 

Explanation :

Multiple of first array :

2 = 2, 4, 6, 8, 10, 12, 14 ...
6 = 6, 12, 18, 24, 30, 36 ...

Factors of second array :

24 = 1, 2, 3, 4, 6, 8, 12, 24
36 = 1, 2, 3, 4, 6, 9, 12, 18, 36

So all common numbers from both arrays are : 6 and 12, so answer is 2.

Example 2 :

a = [2, 4]

b = [16, 32, 96]

There are three numbers between the arrays : 4, 8 and 16. So answer is 3.

Explanation :

Multiple of first array :

2 = 2, 4, 6, 8, 10, 12, 14, 16, 18, 20 ...
4 = 4, 8, 12, 16, 20, 24, 28, 32, 36 ...

Factors of second array :

16 = 1, 2, 4, 8, 16
32 = 1, 2, 4, 8, 16, 32
96 = 1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 48, 96

So all common numbers from both arrays are : 4, 8 and 16, so answer is 3.

See full description on HackerRank :

• Between Two Sets Problem Description 
  

Solution 1 :

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

class Result {

    public static int getTotalX(List<Integer> a, List<Integer> b) {
    
        int lcm = a.get(0);
        for (int number : a) {
            lcm = getLCM(number, lcm);
        }
        
        int gcd = b.get(0);
        for (Integer integer : b) {
          gcd = getGCD(gcd, integer);
        }
        
        int result = 0;
        int multiple = 0;
        while (multiple <= gcd) {
          multiple += lcm;

          if (gcd % multiple == 0)
            result++;
        }

       return result;
    }
    
    static int getLCM(int n1, int n2) {
        if (n1 == 0 || n2 == 0)
          return 0;
        else {
          int gcd = getGCD(n1, n2);
          return Math.abs(n1 * n2) / gcd;
        }
    }
    
    static int getGCD(int n1, int n2) {
        if (n2 == 0) {
          return n1;
        }
        return getGCD(n2, n1 % n2);
    }

}

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        String[] firstMultipleInput = bufferedReader.readLine()
            .replaceAll("\\s+$", "")
            .split(" ");

        int n = Integer.parseInt(firstMultipleInput[0]);

        int m = Integer.parseInt(firstMultipleInput[1]);

        List<Integer> arr = Stream.of(bufferedReader.readLine()
            .replaceAll("\\s+$", "").split(" "))
            .map(Integer::parseInt)
            .collect(toList());

        List<Integer> brr = Stream.of(bufferedReader.readLine()
            .replaceAll("\\s+$", "").split(" "))
            .map(Integer::parseInt)
            .collect(toList());

        int total = Result.getTotalX(arr, brr);

        bufferedWriter.write(String.valueOf(total));
        bufferedWriter.newLine();

        bufferedReader.close();
        bufferedWriter.close();
    }
}

Solution explanation :

• First we loop through first list and find LCM (least common multiple).
• second we loop through second list and find GCD (Greatest common divisor) from that list.
• And last, we do multiple of LCM and check GCD value divide by LCM or not. if GCD is dividable then we increment result by 1.

Output Explanation :

a = [2, 4]
b = [16, 32, 96]

• lcm = 2, gcd = 16, multiple = 0, result = 0
• After execute getLCM we get lcm = 4
• After execute getGCD we get gcd = 16
  
  
• lcm = 4, gcd = 16, multiple = 0, result = 0
• while loop
• multiple += lcm | 0 + 4 = 4
• gcd % multiple == 0 | 16 % 4 == 0 becomes true
• result = 1
  
  
• lcm = 4, gcd = 16, multiple = 4, result = 1
• multiple += lcm | 4 + 4 = 8
• gcd % multiple == 0 | 16 % 8 == 0 becomes true
• result = 2
  
  
• lcm = 4, gcd = 16, multiple = 8, result = 2
• multiple += lcm | 8 + 4 =12
• gcd % multiple == 0 | 16 % 12 == 0 becomes false
  
  
• lcm = 4, gcd = 16, multiple = 4, result = 1
• multiple += lcm | 12 + 4 = 16
• gcd % multiple == 0 | 16 % 16 == 0 becomes true
• result = 3
  
  
• result = 3 

 

See other Hackerrank problem and its solution in Java :

• Java 8 solution for Apple and Orange HackerRank problem  
• Java solution for Breaking best and worst Records HackerRank problem