Between Two Sets | HackerRank Solution

Hello coders, today we are going to solve Between Two Sets HackerRank Solution which is a Part of HackerRank Algorithm Series.

Between Two Sets

Contents

Task

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, 24%6 = 0 and 36%6 = 0 for the first value.
12%2 = 012%6 = 0 and 24%12 = 036%12 = 0 for the second value. Return 2.

Function Description

Complete the getTotalX function in the editor below. It should return the number of integers that are betwen the sets.

getTotalX has the following parameter(s):

  • int a[n]: an array of integers
  • int b[m]: an array of integers

Returns

  • int: the number of integers that are between the sets

Input Format

The first line contains two space-separated integers, n and m, the number of elements in arrays a and b.
The second line contains n distinct space-separated integers a[i] where 0 <= i < n.
The third line contains m distinct space-separated integers b[j] where 0 <= j < m.

Constraints

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

Sample Input

2 3
2 4
16 32 96

Sample Output

3

Explanation

2 and 4 divide evenly into 4, 8, 12 and 16.
4, 8 and 16 divide evenly into 16, 32, 96.

4, 8 and 16 are the only three numbers for which each element of a is a factor and each is a factor of all elements of b.

Solution – Between Two Sets

C++

#include <iostream>
#include <vector>
#include <cmath>
#include <ctime>
#include <cassert>
#include <cstdio>
#include <queue>
#include <set>
#include <map>
#include <fstream>
#include <cstdlib>
#include <string>
#include <cstring>
#include <algorithm>
#include <numeric>

#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

using namespace std;

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;

template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.precision(10);
    cout << fixed;
#ifdef LOCAL_DEFINE
    freopen("input.txt", "rt", stdin);
#endif

    int n, m;
    cin >> n >> m;
    vi a(n); forn(i, n) cin >> a[i];
    vi b(m); forn(i, m) cin >> b[i];
    int ans = 0;
    for1(k, 100) {
        bool ok = true;
        for (int x: a) ok &= k % x == 0;
        for (int x: b) ok &= x % k == 0;
        if (ok) ++ans;
    }
    cout << ans << '\n';

#ifdef LOCAL_DEFINE
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
    return 0;
}

Python

from math import gcd

def get_hcf(arr):
    hcf = arr[0] 
    for i in arr:
        hcf = gcd(hcf,i)
    return hcf

def lcm(a,b):
    return a*b//gcd(a,b)

def get_lcm(arr):
    l = arr[0] 
    for i in arr:
        l = lcm(l,i)
    return l

def getTotalX(a,b):
    lcm_a = get_lcm(a)
    hcf_b = get_hcf(b)
    no_between_sets = sum(1 for i in range(lcm_a, hcf_b+1, lcm_a) if not hcf_b%i and i%lcm_a==0)
    return no_between_sets
    
n,m = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))

print(getTotalX(a,b))

Java

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

public class Solution {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int[] a = new int[n];
        for(int a_i=0; a_i < n; a_i++){
            a[a_i] = in.nextInt();
        }
        int[] b = new int[m];
        for(int b_i=0; b_i < m; b_i++){
            b[b_i] = in.nextInt();
        }
        Arrays.sort(a);
        Arrays.sort(b);
        int count=0;
        for (int i=a[n-1]; i<=b[0]; i++){
            boolean flag=true;
            for (int j=0; j<n; j++){
                if (i%a[j]!=0){
                    flag=false;
                    break;
                }           
            }
            if (flag==true){
                for (int j=0; j<m; j++){
                    if (b[j]%i!=0){
                        flag=false;
                        break;
                    }
                }
            }
            if (flag==true)
                count++;
        }
        System.out.println (count);
    }
}

Disclaimer: The above Problem (Between Two Sets) is generated by Hacker Rank but the Solution is Provided by CodingBroz. This tutorial is only for Educational and Learning Purpose.

Leave a Comment

Your email address will not be published.