Algorithm


Problem Name: Algorithms - Between Two Sets

Problem Link: https://www.hackerrank.com/challenges/between-two-sets/problem?isFullScreen=true

In this HackerRank Functions in Algorithms - Java programming problem solution,

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.

Example

  • a = [2,6]
  • b = [24,36]

There are two numbers between the arrays: 6 and 12.

6%2 = 0 , 6%6 = 0, and 24%6 = 0, 36%6 = 0 for the first value.

12%2 = 0 , 12%6 = 0, and 24%12 = 0, 36%6 = 0 for the second value. Return 2.

Constraints

  • 1 <= n,m <= 10
  • 1 <= a[i] <= 100
  • 1 <= b[j] <= 100

 

 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming


#include <iostream>
using namespace std;

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

int lcm(int a, int b) { return a * b / gcd(a, b); }

int main() {
  int n, m, a[10], b[10];
  cin >> n >> m;
  for (int i = 0; i  <  n; i++) {
    cin >> a[i];
  }
  for (int i = 0; i  <  m; i++) {
    cin >> b[i];
  }
  int lcmA = a[0];
  for (int i = 1; i  <  n; i++) {
    if (lcmA > 100) {
      lcmA = 101;
      break;
    }
    lcmA = lcm(lcmA, a[i]);
  }
  int gcdB = b[0];
  for (int i = 1; i  <  m; i++) {
    gcdB = gcd(gcdB, b[i]);
  }
  int cnt = 0;
  for (int i = lcmA; i  < = gcdB; i += lcmA) {
    bool flag = true;
    for (int j = 0; j  <  m; j++) {
      if (b[j] % i != 0) {
        flag = false;
        break;
      }
    }
    if (flag) {
      cnt++;
    }
  }
  cout << cnt << endl;
  return 0;
}
Copy The Code & Try With Live Editor

#2 Code Example with Java Programming

Code - Java Programming


import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;

public class Solution {

    /*
     * Complete the getTotalX function below.
     */
    static int getTotalX(int[] a, int[] b) {
        boolean var,var2;int i;int j;int m = 0;
        for(i = a[a.length-1]; i  < = b[0]; i++){
            var = false;
            for(j = 0; j <  a.length; j++){
                if(i%a[j] == 0){
                    var = true;
                }else{
                    var = false;
                    break;
                }
            }
            if(var == true){
                var2 = false;
                for(int k = 0; k < b.length; k++){
                    if(b[k]%i == 0){
                        var2 = true;
                    }else{
                        var2 = false;
                        break;
                    }
                   
                }
                 if(var2 == true){
                        m++;
                    }
            }
        }
       return m;
    }

    private static final Scanner scan = new Scanner(System.in);

    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        String[] nm = scan.nextLine().split(" ");

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

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

        int[] a = new int[n];

        String[] aItems = scan.nextLine().split(" ");

        for (int aItr = 0; aItr  <  n; aItr++) {
            int aItem = Integer.parseInt(aItems[aItr].trim());
            a[aItr] = aItem;
        }

        int[] b = new int[m];

        String[] bItems = scan.nextLine().split(" ");

        for (int bItr = 0; bItr  <  m; bItr++) {
            int bItem = Integer.parseInt(bItems[bItr].trim());
            b[bItr] = bItem;
        }

        int total = getTotalX(a, b);

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

        bw.close(>;
    }
}
Copy The Code & Try With Live Editor

#3 Code Example with C# Programming

Code - C# Programming


using System;
using System.Linq;

class Solution
{
    static void Main(String[] args)
    {
        //No need to capture number of elments in set A and B as I use foreach loop to iterate them.
        Console.ReadLine();
        var a_temp = Console.ReadLine().Split(' ');
        var setA = Array.ConvertAll(a_temp, Int32.Parse);
        var b_temp = Console.ReadLine().Split(' ');
        var setB = Array.ConvertAll(b_temp, Int32.Parse);
        int total = getTotalX(setA, setB);
        Console.WriteLine(total);
    }

    static int getTotalX(int[] a, int[] b)
    {
        var totalXs = 0;
        var maximumA = a.Max(); //Time-complexity O(n)
        var minimumB = b.Min(); //Time-complexity O(m)
        var counter = 1;
        var multipleOfMaxA = maximumA;

        while (multipleOfMaxA  < = minimumB)
        {
            var factorOfAll = true;

            foreach (var item in a) //Time complexity O(n)
            {
                if (multipleOfMaxA % item != 0)
                {
                    factorOfAll = false;
                    break;
                }
            }

            if (factorOfAll)
            {
                foreach (var item in b) //Time complexity O(m)
                {
                    if (item % multipleOfMaxA != 0)
                    {
                        factorOfAll = false;
                        break;
                    }
                }
            }

            if (factorOfAll)
                totalXs++;

            counter++;
            multipleOfMaxA = maximumA * counter; //Here counter is the x factor which contributes to O(x(n+m)) complexity.
        }
        return totalXs;
    }
}
Copy The Code & Try With Live Editor

#4 Code Example with Python Programming

Code - Python Programming


import sys

def check_a(number, a):
    for el in a:
        if number % el != 0:
            return False
    return True

def check_b(number, b):
    for el in b:
        if el % number != 0:
            return False
    return True

def getTotalX(a, b):
    res = 0
    max_a = max(a)
    min_b = min(b)
    
    probe = max_a
    
    while probe <= min_b:
        if check_a(probe, a) and check_b(probe, b):
            res += 1
        probe += max_a
        
    return res
    

if __name__ == "__main__":
    n, m = input().strip().split(' ')
    n, m = [int(n), int(m)]
    a = list(map(int, input().strip().split(' ')))
    b = list(map(int, input().strip().split(' ')))
    total = getTotalX(a, b)
    print(total)
Copy The Code & Try With Live Editor

#5 Code Example with PHP Programming

Code - PHP Programming



Copy The Code & Try With Live Editor
Advertisements

Demonstration


Previous
[Solved] Number Line Jumps in C++,Java, Python, PHP & C# solution in Hackerrank
Next
[Solved] Grading Students in SQL solution in Hackerrank