why did you multiply 2 with the i in the loop ?

why not

for (int i=f;i<=l;i+=f)

instead of

for(int i = f, j =2; i<=l; i=f*j,j++)

? Otherwise a very nice solution :)

100*99*97*91*89*83*79*73*71*67~1.7*1e19, so if b = {100, 99, 97, 91, 89, 83, 79, 73, 71, 67} lcm(b) be over integer range

copy paste maar dia bhai

This is a very lengthy approach to the problem.

in my code time complexity is quite less:

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

public class Solution {

static int getTotalX(int[] a, int[] b) {

    int i,j,k;
    Vector <Integer> v1 = new Vector <Integer> ();

    for(i=1;i<=b[(b.length-1)];i++)
    {
        int c=0;
        for(j=0;j<b.length;j++)
        {
            if(b[j]%i==0)
            {
                c++;
            }
        }
        if(c==b.length)
        {
        v1.add(i);    
        }
    }
    int c1;
    int c2=0;
    for(k=0;k<v1.size();k++)
    {
        c1=0;
        int a1= v1.get(k);
        for(i=0;i<a.length;i++)
        {
            if(a1%a[i]==0)
            {
                c1++;
            }
        }
        if(c1==a.length)
        {
            c2++;
        }

    }
    return c2;
    // Complete this function
}

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();
    }
    int total = getTotalX(a, b);
    System.out.println(total);
    in.close();
}

}

Redundant memory allocation. There is no need to use arrays.

i didnt get why j=2 in this line bellow

for (int i = f, j = 2; i <= l; i = f * j, j++) {

could someone clarify me?

I am a beginner. So can anyone tell me if this is more efficient than the above code or not?

....... ....... for (int i = 0; imaxA){ maxA=a[i]; }

 public static int lcm(int[] ai){
     int lcm1= maxA;
     int lcmMin=lcm1;
        while(true){

            for (int  i =0; i<ai.length;i++){
                if(lcm1%ai[i]==0){
                    countA++;
                }
            }
            if (countA==ai.length){
                lcmMin=lcm1;
                break;
            }
            else{
                lcm1++;
            }
        }
     return lcmMin;
    }

How does this for loop works?

for(int i = f, j =2; i<=l; i=f*j,j++)

I have the same solution but i don't want the complexity is O(nlogn). can explain?

Another approach to this problem is using C++ and vectors Also, I think simply using factors instead of finding GCD and LCM can be a more simpler as well as transparent way:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void factorsOf(int number, vector<int> &arr)
{
int temp, i=0;
for(temp=1;temp <= number;temp++)
{
                if ((number % temp) == 0 )
                {
                        arr.push_back(temp);
                        i++;
                }
    }
}

int getTotalX(vector<int> &a, vector<int> &b)
{
vector<int> allFactors; //THIS VECTOR COLLECTS ALL THE FACTORS OF THE ELEMENTS OF BOTH THE ARRAYS.
vector <int> temp;
int size_a = a.size();
int size_b = b.size();
int count=0,i=0,j=0,flag1,flag2;
//COLLECTING ALL THE FACTORS OF ALL THE ELEMENTS OF BOTH THE ARRAYS, SO AS TO LIMIT THE ITERATIONS NEEDED FOR SOLVING THE PROBLEM
while(size_a != 0)  //RUNNING THROUGH THE ENTIRE ARRAY
{
    factorsOf(a[size_a-1], temp);
    //NOW, TEMP HAS STORED THE FACOTRS OF THE NUMBER SENT TO THE FUNCTION
    allFactors.insert(allFactors.end(), temp.begin(), temp.end());
    size_a--;
}
//REPEATING THE SAME PROCESS FOR ARRAY B
while(size_b != 0)
{
    ////cout<< endl<< size_b-1 << ",  Value: "<< b[size_b-1];
    factorsOf(b[size_b-1], temp);
    //NOW, TEMP HAS STORED THE FACOTRS OF THE NUMBER SENT TO THE FUNCTION
    allFactors.insert(allFactors.end(), temp.begin(), temp.end());
    size_b--;
}

//NOW SORTING, REMOVING DUPLICATES AND FINALLY RESIZING THE VECTOR
sort(allFactors.begin(), allFactors.end());

allFactors.erase(unique(allFactors.begin(), allFactors.end()), allFactors.end() );

for(int j=0;j<allFactors.size();j++)
{
    flag1 = 1;

    for(i=0;i<a.size();i++)
    {
        if(allFactors[j] % a[i] != 0)
        {
            flag1 = 0;
            break;
        }
    }
    if(flag1 == 1)
    {
        flag2 = 1;
        for(i=0;i<b.size();i++)
        {
            if(b[i] % allFactors[j] != 0)
            {
                flag2 = 0;
                break;
            }
        }
        if(flag2 == 1)
        {
            count++;
            cout<< endl<<"RESULT: "<< allFactors[j];
        }
    }
}

return count;

}

int main()
{
            vector <int> a = {2, 4};
   vector <int> b = {16, 32, 96};
     int total = getTotalX(a, b);

            cout <<endl<<"THE TOTAL IS: " <<total << "\n";
     }

perhaps easier to understand, but your organization is on point. Uses built-in gcd:

#!/bin/python

import sys
from fractions import gcd

n,m = raw_input().strip().split(' ')
n,m = [int(n),int(m)]
A = map(int,raw_input().strip().split(' '))
B = map(int,raw_input().strip().split(' '))

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

lcm = reduce(LCM, A, 1)
gcd = reduce(gcd, B)

lcm_copy = lcm

count = 0
while lcm <= gcd:
    if(gcd % lcm) == 0:
        count += 1
    lcm = lcm + lcm_copy

print(count)

What is this syntax?

def gcd(a: int, b: int) -> int:

I have never seen that before in python3, couldyou ellaborate on what it is for? At first i thought that gcd only accepted a and b to be an integer. But when I tried setting a to an float, no error accured.

• What is it for?

Here is smaller code bro,

def getTotalX(a, b):
    total = 0
    for x in list(range(a[-1], b[0] + 1)):
        hold = 0
        for v in a:
            if (x % v == 0): hold += 1
            else: hold = 0; break    
        
        for c in b:
            if (c % x == 0): hold += 1
            else: hold = 0; break       
        if (hold == len(a) + len(b)):
            total += 1   
    return total

"lcm(a: int, b: int) -> int" , what is the concept in python behind this??

Will the solution return correct values when we use the below test case: 3 3 7 8 10 280 560 1120

I think the solution above would give incorrect results.

Cool code!! my code to find number of factors def nooffactors(z): print(sum(int(z)%i == 0 for i in range(1,z+1) )) return

This is far far more readable than prior solutions. I like it. SImilar to mine in c#

    static int getTotalX(int[] a, int[] b) 
{
    var lcm = LCM(a);
    var gcf = GCF(b);

    var candidate = lcm;
    var count = 0;
    while (candidate<=gcf)
    {
        count += gcf % candidate ==0 ? 1 :0;
        candidate += lcm;
    }
    return count;
}

static int LCM(int []x) => x.Aggregate(lCM);
static int GCF(int []x) => x.Aggregate(gCF);
static int gCF(int a, int b) => b == 0 ? a : gCF(b, a % b);  
static int lCM(int a, int b) => (a *b) / gCF(a, b);

So thats what he meant(calculating the counter that way). Not sure, but some how I misunderstood "Integer being considered". Being a newbie here, just didn't notice this section. A lot has already been said and done, and I was going crazy over the tests. :-)

Your lcm and gcd functions looks fine. But the way you calculated the lcm or gcd for the whole array is not correct. In your current implementation you will get the lcm or gcd only for the last two elements of the array. Try to find how to calculate those for the whole array.

For step-3, if f evenly divides g, then count the number of multiples of f which evenly divides g. Evenly divides means if g is divided by f then the remainder will be 0.

g%f == 0

and multiple of f means f,2*f,3*f,4*f... so on. In your case you you have to count the number of multiple of f which evenly divides g. like

g%(f*i)==0, where i=1,2,3... until i*f<=g;

EDIT - 1:

I've updated my code for better readability: I guees this will explain it a lot better.

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

public class Solution {
    
    private boolean canADivideI(int i, int[] a, int n){
        boolean answer = false;
        for(int j=0;j<n;j++){
                if(i%a[j] == 0){
                    if(j==n-1){
                        answer = true;
                    }
                }
                else{j=n;}
        }
        return answer;
    }
    
    private boolean canIDivideB(int i, int[] b, int m){
        boolean answer = false;
        for(int k=0;k<m;k++){
            if(b[k]%i ==0){
                if(k==m-1){
                    answer = true;
                }
            }
            else {k=m;}
        }   
        return answer;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        Solution s = new Solution();
        int n = in.nextInt();
        int m = in.nextInt();
        int[] a = new int[n];
        int max = 100, min = 0, elementsFound = 0;
        for(int a_i=0; a_i < n; a_i++){
            a[a_i] = in.nextInt();
            //Look for Max in A and set that as the MIN 
            if(min < a[a_i]) {min = a[a_i];}
        }
        int[] b = new int[m];
        for(int b_i=0; b_i < m; b_i++){
            b[b_i] = in.nextInt();
            //Look for Min in B and set that as the MAX
            if(max > b[b_i]) {max = b[b_i];}
        }
        for(int i = min; i <=max; i++){
            if(s.canADivideI(i, a, n) && s.canIDivideB(i, b, m)){
                elementsFound++;   
            }
        }
        System.out.println(elementsFound);
    }
}

I did something simmilar, I guess it is an optimized version.

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];
        int max = 100, min = 0, answr = 0;
        for(int a_i=0; a_i < n; a_i++){
            a[a_i] = in.nextInt();
            //Look for Max in A and set that as the MIN 
            if(min < a[a_i]) {min = a[a_i];}
        }
        int[] b = new int[m];
        for(int b_i=0; b_i < m; b_i++){
            b[b_i] = in.nextInt();
            //Look for Min in B and set that as the MAX
            if(max > b[b_i]) {max = b[b_i];}
        }
        for(int i = min; i <= max; i++){
            for(int j = 0; j < n; j++){
                if(i%a[j] == 0){
                    if(j == n-1){
                        for(int k = 0; k < m; k++){
                            if(b[k]%i == 0){
                                if(k == m-1){
                                    answr++;
                                }
                            }
                            else {k = m;}
                        }
                    }
                }
                else{j = n;}
            }
        }
        System.out.println(answr);
    }
}

All is good. but, possibly its good practice to eliminate imagining min or max.

for this

// set the first value of array as min or max then start //comparing from next element

b[0] = in.nextInt(); minB = b[0];

// then

for(int b_i = 1; b_i < m ; b_i++ ) { int tmp = in.nextInt(); minB = tmp < minB ? tmp:minB; b[b_i] = tmp; }

:)

I found similar solution but used the min value from b to loop:

static int getTotalX(int[] a, int[] b) {
    int result = 0;
    int min = IntStream.of(b).min().getAsInt();

    outer:
    for ( int j = 1; j <= min; j++ ) {
        for (int i : b) {
        	if (i % j != 0) {
            	continue outer;
            }
       	}

        for (int i : a) {
    	    if (j % i != 0) {
            	continue outer;
            }
        }

        result++;
	}

    return result;
}

actually for both of the steps 1 & 2 the complexity will be O(n log(b)).

Here n is the length of the array and b is the smaller integer of a pair(a,b) for which we calculate the GCD/LCM.

For simplicity we call it O(n log(n)) instead of O(n log(b)).

Explanation: To calculate the GCD or LCM for the whole array we need to run a loop up to the length of the array which is n and inside that loop we need to calculate GCD/LCM which will take log(n). like below.

previousGCD = array[0];
for(int i = 1; i<n; i++) {// n
	previousGCD = GCD(previousGCD, array[i]);//log(n) 
}

so the complexity is O(n*log(n)). Same goes for LCM also.

Elegant code with perfect comments :) I'm new to DP. Shouldn't we use memoization here to optimize the runtime? Or is this the best solution possible? Pls clear me out here!!

Hey, where are you learning scala? Thats the language I want to learn the most right now.

Please read the problem description carefully. Specially the conditions.

1. All elements in A are factors of x.
2. x is a factor of all elements in B.

Now look at the condition-2, Do you think 8 is a factor of all elements in B{20, 40}?

Another thing, the answer for your test case will not be 1, it will be 2 as multiples are 4 and 20(you excluded 20).

What do you think about recursive approach? I think its better code. For such small array sizes its not that much slower.

int between(vector < int > a, vector < int > b, int x){
    if(x <= 100)
    {
        bool good_x = true;
        for(int i = 0; i < a.size(); ++i)
            good_x &= x%a[i] == 0;
        for(int i = 0; i < b.size(); ++i)
            good_x &= b[i]%x == 0;
        return good_x + between(a, b, x+1);
    }
    else
        return 0;
}

Nice one

In this case I think is more readable non recursive solution:

vector<int> A(m);
vector<int> B(n);
/// [...]
auto lcmOfA = lcm_element(A);
auto gcdOfB = gcd_element(B);
    
auto counter = 0;
auto multipleOfLcm = lcmOfA;
    
while (multipleOfLcm <= gcdOfB)
{
    counter += is_divisible(gcdOfB, multipleOfLcm);
    multipleOfLcm += lcmOfA;
}

For both cases LCM(A) = GCD(B)+1 and GCD(B) - LCM(A) <<<< LCM(A) the result would be 0.

For step-3 you need to run a loop from LCM upto GCD each time multiplying the LCM by 1,2,3.. so on. See the sudo code below.

GCD%(LCM*i)==0, where i=1,2,3... until LCM*i<=GCM;

If you think running a loop means brute forcing, then yes you have to use brute force. :)

Suppose L is your calculated LCM of array A and G is your calulate GCD of array B. Then the result will be number of multiples of L which will evenly devides G. Here evenly devides meaning the remainder will be zero if you devide x by y.

Pseudo code

count = 0;
for i = 1 to L*i<=G
   if(G%(L*i) == 0) 
       count = count+1;
return count;