Algorithm
Problem Name: Algorithms -
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:
- 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 , 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