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.
GCD Matrix
GCD Matrix
+ 0 comments Here is GCD matrix problem solution - https://programs.programmingoneonone.com/2021/07/hackerrank-GCD-matrix-problem-solution.html
+ 0 comments If you know about Mobius function and Inclusive-Exclusive Principle, solving this problem is more comfortable !
+ 0 comments I "purchased" two test cases, but the sample input is truncated for both. What good is that?
Edit: There's a link to download the complete sample input, it's just difficult to see!
+ 0 comments I tried a JavaScript example (NodeJS).
It works locally (node6) but Hacker Rank keeps timing out.
'use strict'; // .... function main() { const nmq = readLine().split(' '); const n = parseInt(nmq[0], 10); const m = parseInt(nmq[1], 10); const q = parseInt(nmq[2], 10); const a = readLine().split(' ').map(aTemp => parseInt(aTemp, 10)); const b = readLine().split(' ').map(bTemp => parseInt(bTemp, 10)); const matrix = []; for (let qItr = 0; qItr < q; qItr++) { const r1C1R2C2 = readLine().split(' '); const r1 = parseInt(r1C1R2C2[0], 10); const c1 = parseInt(r1C1R2C2[1], 10); const r2 = parseInt(r1C1R2C2[2], 10); const c2 = parseInt(r1C1R2C2[3], 10); matrix.push(/* SOME STUFF */); } return testResolver(matrix, a, b); } function testResolver(matrix, a, b){ return matrix.map(({m1, m2}, index) => { const queriedSetObj = {}; for (let p1 = m1.xPos; p1 <= m2.xPos; p1++) { for (let p2 = m1.yPos; p2 <= m2.yPos; p2++) { const gcd = greatestCommonDenominator(a[p1], b[p2]); if (!(gcd in queriedSetObj)) { queriedSetObj[gcd] = gcd; } } } const result = Object.keys(queriedSetObj).length; console.log(result); return result; }); }
Kept running out of memory locally; but eventually the above works.
Load more conversations
Sort 13 Discussions, By:
Please Login in order to post a comment