We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Implemented the algorithm in a similar way, however, I am not quite sure I understand your time complexity analysis. What is n in your comment?
One can calculate lcm/gcd of two numbers in O(n^2), where n is the number of bits (simplest Euclidian algorithm). But given the fact that we have fixed bit size integers we might consider this be a constant, say C1
Now, lets assume that LA - is the length of array A, and LB - length of array B, them the overal time complexity will be O(C1*(LA + LB) + ((GCD(B) / LCM(A))). We might probabably want to discard the constant factor for counting multiples because we have restriction of numbers being less than 100, however for a more general case and huge numbers this might be a factor
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Between Two Sets
You are viewing a single comment's thread. Return to all comments →
Implemented the algorithm in a similar way, however, I am not quite sure I understand your time complexity analysis. What is n in your comment?
One can calculate lcm/gcd of two numbers in O(n^2), where n is the number of bits (simplest Euclidian algorithm). But given the fact that we have fixed bit size integers we might consider this be a constant, say C1
Now, lets assume that LA - is the length of array A, and LB - length of array B, them the overal time complexity will be O(C1*(LA + LB) + ((GCD(B) / LCM(A))). We might probabably want to discard the constant factor for counting multiples because we have restriction of numbers being less than 100, however for a more general case and huge numbers this might be a factor