Between Two Sets
Between Two Sets
+ 76 comments O(n log(n)) solution.
1. find the LCM of all the integers of array A.
2. find the GCD of all the integers of array B.
3. Count the number of multiples of LCM that evenly divides the GCD.
+ 11 comments I found this outrageously difficult for being "easy" and I would have not even begun to understand what I was supposed to do without reading the discussions. "Factor" ? "Between two sets"? Why not call things by their name : GCD, LCM ?
Congratulations to those who solved this problem without help, this was way over my head.
+ 30 comments For all those guys like me who found this question difficult to understand, here's the simple explanation i got after searching for decades.
1. Find LCM of the first array a. 2.Find GCD / HCF of the second array b. 3.Find all the multiples of LCM up to GCD, which divides the GCD evenly.
For Example: Here, In the given sample Input, The LCM of array a would be 4 and the GCD of the array b would be 16. Now, Find all Multiples of 4,(like 4,8,12,16,...) upto 16, such that, (16%multiple_of_4_here) should be 0. Here, 16%4=0 -----> count=1 (suppose this variable.) 16%8=0 -----> count=2 16%12!=0 ---> count=2 16%16=0 ---> count=3.
Thus, The answer is 3. Hope this helped you.
+ 24 comments My javascript solution:
function getTotalX(a, b) { let validCount = 0; for (let x = 1; x <= 100; x++) { if (a.every(int => (x % int == 0))) { if (b.every(int => (int % x == 0))) { validCount++; } } } return validCount; }
+ 14 comments Python with comprehension lists, for each number between max(setA) and min(setB), it will create a list that will hold boolean values, and 'all' checks that all the boolean values in a list are true.
lenA, lenB = map(int, raw_input().split()) setA = map(int, raw_input().split()) setB = map(int, raw_input().split()) maxA = max(setA) minB = min(setB) count = 0 for num in range(maxA, minB + 1): left = all([num % numA == 0 for numA in setA]) right = all([numB % num == 0 for numB in setB]) count += left*right print count
Sort 2372 Discussions, By:
Please Login in order to post a comment