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.
1) The salaries after normalization are actually just the gcd - note the process is reminiscent of the naïve euclidean algorithm, or that it preserves divisors + reduces numbers until everything is equal => everything ends up at an equal number which is divided by every divisor of the original set, which is the gcd
2) gcd(a1+k, a2+k, ..., an+k) = gcd(a1+k, (a2+k)-(a1+k), ..., (an+k)-(a1+k)) = gcd(a1+k, a2-a1, ..., an-a1) = gcd(a1+k, gcd(a2-a1, an-a1)). You can precompute the second bit of the gcd and then you only have to do a gcd with two elements for each of the queries, which is fast enough to pass.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Salary Blues
You are viewing a single comment's thread. Return to all comments →
1) The salaries after normalization are actually just the gcd - note the process is reminiscent of the naïve euclidean algorithm, or that it preserves divisors + reduces numbers until everything is equal => everything ends up at an equal number which is divided by every divisor of the original set, which is the gcd
2) gcd(a1+k, a2+k, ..., an+k) = gcd(a1+k, (a2+k)-(a1+k), ..., (an+k)-(a1+k)) = gcd(a1+k, a2-a1, ..., an-a1) = gcd(a1+k, gcd(a2-a1, an-a1)). You can precompute the second bit of the gcd and then you only have to do a gcd with two elements for each of the queries, which is fast enough to pass.