Skip to content
  • Home
  • Contact Us
  • About Us
  • Privacy Policy
  • DMCA
  • Linkedin
  • Pinterest
  • Facebook
thecscience

TheCScience

TheCScience is a blog that publishes daily tutorials and guides on engineering subjects and everything that related to computer science and technology

  • Home
  • Human values
  • Microprocessor
  • Digital communication
  • Linux
  • outsystems guide
  • Toggle search form
HackerRank GCD Matrix Problem Solution

HackerRank GCD Matrix Problem Solution

Posted on August 6, 2023August 6, 2023 By Yashwant Parihar No Comments on HackerRank GCD Matrix Problem Solution

In this post, we will solve HackerRank GCD Matrix Problem Solution.

Alex has two arrays defined as A = [ao, a1,…, an-1] and B = [bo, b1, bm-1]. He
created an n x m matrix, M, where M = gcd(a, b) for each i, j in M. Recall that
gcd (a, b) is the greatest common divisor of a and b.
For example, if A = [2, 3] and B = [5, 6], he builds M = [[1, 2], [1, 3]] like so:
Alex’s friend Kiara loves matrices, so he gives her q questions about matrix M where each question is in the form of some submatrix of M with its upper-left corner at Me, and its bottom-right corner at Mr₂,c₂- For each question, find and print the number of distinct integers in the given submatrix on a new line.
Input Format
The first line contains three space-separated integers describing the respective values of n (the size of array A), m (the size of array B), and q (Alex’s number of questions). The second line contains n space-separated integers describing a0, a1,…,an-1. The third line contains m space-separated integers describing bo, b1,…, bm-1. Each line i of the q subsequent lines contains four space-separated integers describing the respective values of r₁, c₁, r₂, and c₂ for the ith question (ie., defining a submatrix with upper-left corner (r1, C1) and bottom-right corner (r2, C2)).

Output Format

For each of Alex’s questions, print the number of distinct integers in the given submatrix on a new line.

Sample Input 0

3 3 3
1 2 3
2 4 6
0 0 1 1
0 0 2 2
1 1 2 2

Sample Output 0

2
3
3
HackerRank GCD Matrix Problem Solution
HackerRank GCD Matrix Problem Solution

Table of Contents

  • GCD Matrix C Solution
  • GCD Matrix C++ Solution
  • GCD Matrix C Sharp Solution
  • GCD Matrix Java Solution
  • GCD Matrix Python Solution

GCD Matrix C Solution

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int a[100000],b[100000];
long long dp1[100000],dp2[100000],dp[100000];

int main(){
  int n,m,q,r1,r2,c1,c2,ans,i,j;
  scanf("%d%d%d",&n,&m,&q);
  for(i=0;i<n;i++)
    scanf("%d",a+i);
  for(i=0;i<m;i++)
    scanf("%d",b+i);
  while(q--){
    memset(dp1,0,sizeof(dp1));
    memset(dp2,0,sizeof(dp2));
    memset(dp,0,sizeof(dp));
    scanf("%d%d%d%d",&r1,&c1,&r2,&c2);
    for(i=r1;i<=r2;i++)
      for(j=1;j*j<=a[i];j++)
        if(a[i]%j==0){
          dp1[j-1]++;
          if(j*j!=a[i])
            dp1[a[i]/j-1]++;
        }
    for(i=c1;i<=c2;i++)
      for(j=1;j*j<=b[i];j++)
        if(b[i]%j==0){
          dp2[j-1]++;
          if(j*j!=b[i])
            dp2[b[i]/j-1]++;
        }
    for(i=99999,ans=0;i>=0;i--){
      dp[i]+=dp1[i]*dp2[i];
      if(dp[i]>0){
        ans++;
        dp[0]-=dp[i];
        for(j=2;j*j<=i+1;j++)
          if((i+1)%j==0){
            dp[j-1]-=dp[i];
            if(j*j!=i+1)
              dp[(i+1)/j-1]-=dp[i];
          }
      }
    }
    printf("%d\n",ans);
  }
  return 0;
}

GCD Matrix C++ Solution

#include <bits/stdc++.h>
// #include "testlib.h"  
using namespace std ;

#define ft first
#define sd second
#define pb push_back
#define all(x) x.begin(),x.end()

#define ll long long int
#define vi vector<int>
#define vii vector<pair<int,int> >
#define pii pair<int,int>
#define plii pair<pair<ll, int>, int>
#define piii pair<pii, int>
#define viii vector<pair<pii, int> >
#define vl vector<ll>
#define vll vector<pair<ll,ll> >
#define pll pair<ll,ll>
#define pli pair<ll,int>
#define mp make_pair
#define ms(x, v) memset(x, v, sizeof x)

#define sc1(x) scanf("%d",&x)
#define sc2(x,y) scanf("%d%d",&x,&y)
#define sc3(x,y,z) scanf("%d%d%d",&x,&y,&z)

#define scll1(x) scanf("%lld",&x)
#define scll2(x,y) scanf("%lld%lld",&x,&y)
#define scll3(x,y,z) scanf("%lld%lld%lld",&x,&y,&z)

#define pr1(x) printf("%d\n",x)
#define pr2(x,y) printf("%d %d\n",x,y)
#define pr3(x,y,z) printf("%d %d %d\n",x,y,z)

#define prll1(x) printf("%lld\n",x)
#define prll2(x,y) printf("%lld %lld\n",x,y)
#define prll3(x,y,z) printf("%lld %lld %lld\n",x,y,z)

#define pr_vec(v) for(int i=0;i<v.size();i++) cout << v[i] << " " ;

#define f_in(st) freopen(st,"r",stdin)
#define f_out(st) freopen(st,"w",stdout)

#define fr(i, a, b) for(i=a; i<=b; i++)
#define fb(i, a, b) for(i=a; i>=b; i--)
#define ASST(x, l, r) assert( x <= r && x >= l )

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

const int mod = 1e9 + 7;

int ADD(int a, int b, int m = mod) {
    int s = a;
    s += b;
    if( s >= m )
      s -= m;
    return s;
}

int MUL(int a, int b, int m = mod) {
    return (1LL * a * b % m);
}

int power(int a, int b, int m = mod) {
    int res = 1;
    while( b ) {
        if( b & 1 ) {
            res = 1LL * res * a % m;
        }
        a = 1LL * a * a % m;
        b /= 2;
    }
    return res;
}

ll nC2(ll x) {
    return ( x * ( x - 1 ) / 2 );
}

const int maxn = 1e5 + 5;

int A[maxn], B[maxn];
ll d[maxn];
int a[maxn], b[maxn];
int n, m, q;
void reset() {
    int i; fr(i, 1, maxn-1) {
        a[i] = b[i] = d[i] = 0;
    } 
}

void solve() {
    reset();
    int i, w, x, y, z;
    cin >> w >> x >> y >> z; w++; x++; y++; z++;
    assert(1 <= w && w <= n);
    assert(1 <= y && y <= n);
    assert(w <= y && x <= z);
    assert(1 <= x && x <= m);
    assert(1 <= z && z <= m);
    fr(i, w, y) a[A[i]] ++;
    fr(i, x, z) b[B[i]] ++;
    fr(i, 1, maxn-5) {
        int j = i, v1 = 0, v2 = 0;
        while( j <= maxn-5 ) {
            v1 += a[j];
            v2 += b[j];    
            j += i;
        } 
        a[i] = v1; b[i] = v2;
    }

    int cnt = 0;
    fb(i, maxn-5, 1) {
        int j = i; ll ans = 0;
        ans = 1LL * a[i] * b[i];
        while(j <= maxn-5) {
            ans -= d[j];
            j += i;
        }
        d[i] = ans;
        if( d[i] ) cnt ++;
    }
    cout << cnt << "\n";
}
int main() {
    cin >> n >> m >> q;
    assert(1 <= n && n <= 100000);
    assert(1 <= m && m <= 100000);
    assert(q <= 10 && q >= 1);
    int i; 
    fr(i, 1, n) {
        cin >> A[i];
        assert(A[i] <= 100000 && A[i] >= 1);
    }
    fr(i, 1, m) {
        cin >> B[i];
        assert(B[i] <= 100000 && B[i] >= 1);
    }
    while( q-- ) solve();
    return 0;
}

GCD Matrix C Sharp Solution

using System;
using System.Linq;

namespace HackerRank
{
    class GcdMatrix
    {
        static void Main(string[] args)
        {
            var tokens = Console.ReadLine().Split(' ').ToArray();

            var N = Convert.ToInt32(tokens[0]);
            var M = Convert.ToInt32(tokens[1]);
            var Q = Convert.ToInt32(tokens[2]);

            var A = Console.ReadLine().Split(' ').Select(x => Convert.ToInt32(x)).ToArray();
            var B = Console.ReadLine().Split(' ').Select(x => Convert.ToInt32(x)).ToArray();

            for (var q = 0; q < Q; q++)
            {
                tokens = Console.ReadLine().Split(' ').ToArray();

                var r1 = Convert.ToInt32(tokens[0]);
                var c1 = Convert.ToInt32(tokens[1]);

                var r2 = Convert.ToInt32(tokens[2]);
                var c2 = Convert.ToInt32(tokens[3]);

                var MAX = Math.Max(A.Skip(r1).Take(r2 - r1 + 1).Max(), B.Skip(c1).Take(c2 - c1 + 1).Max());

                var freqA = new int[MAX + 1];

                for (var i = r1; i <= r2; i++)
                {
                    freqA[A[i]]++;
                }

                var freqB = new int[MAX + 1];

                for (var j = c1; j <= c2; j++)
                {
                    freqB[B[j]]++;
                }

                var numberOfItemsGCDDividesInA = new long[MAX + 1]; // numberOfItemsGCDDividesInA[x] -> number of items divided by x in A.
                var numberOfItemsGCDDividesInB = new long[MAX + 1]; // numberOfItemsGCDDividesInB[x] -> number of items divided by x in B.

                // For every possible GCD
                for (var k = 1; k <= MAX; k++)
                {
                    var gcd = k;

                    do
                    {
                        numberOfItemsGCDDividesInA[k] += freqA[gcd];
                        numberOfItemsGCDDividesInB[k] += freqB[gcd];
                        gcd += k;
                    }
                    while (gcd <= MAX);
                }

                var numberOfPairsPerGCD = new long[MAX + 1];

                // For every possible GCD, in descending order
                for (var k = MAX; k >= 1; k--)
                {
                    var gcd = k;

                    numberOfPairsPerGCD[k] = numberOfItemsGCDDividesInA[k] * numberOfItemsGCDDividesInB[k];

                    gcd += gcd;

                    while (gcd <= MAX)
                    {   // Don't count the pairs already handled by larger GCDs.
                        numberOfPairsPerGCD[k] -= numberOfPairsPerGCD[gcd];
                        gcd += k;
                    }
                }

                var numberOfDistinctDivisors = numberOfPairsPerGCD.Count(x => x > 0);

                Console.WriteLine(numberOfDistinctDivisors);
            }
        }
    }
}

GCD Matrix Java Solution

import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;

public class C2 {
    InputStream is;
    PrintWriter out;
    String INPUT = "";
    
    void solve()
    {
        int n = ni(), m = ni(), Q = ni();
        int[] a = na(n);
        int[] b = na(m);
        for(int z = 0;z < Q;z++){
            int dist = 0;
            int r1 = ni(), c1 = ni(), r2 = ni(), c2 = ni();
            int[] fr = make(a, r1, r2);
            int[] fc = make(b, c1, c2);
            long[] f = new long[100005];
            for(int i = 0;i < 100005;i++)f[i] = (long)fr[i] * fc[i];
            for(int i = 100004;i >= 1;i--){
                for(int j = 2*i;j < 100005;j+=i){
                    f[i] -= f[j];
                }
            }
            for(int i = 0;i < 100005;i++){
                assert f[i] >= 0;
                if(f[i] > 0)dist++;
            }
            out.println(dist);
        }
    }
    
    int[] make(int[] a, int l, int r)
    {
        int[] f = new int[100005];
        for(int i = l;i <= r;i++){
            for(int d = 1;d*d <= a[i];d++){
                if(a[i] % d == 0){
                    f[d]++;
                    if(d*d < a[i])f[a[i]/d]++;
                }
            }
        }
        return f;
    }
    
    public static long gcd3(long a, long b) {
        if(a == 0)return b;
        if(b == 0)return a;
        
        int ashift = Long.numberOfTrailingZeros(a);
        int bshift = Long.numberOfTrailingZeros(b);
        a >>>= ashift;
        b >>>= bshift;
        while(b != a){
            if(a > b){
                long t = a; a = b; b = t;
            }
            b -= a;
            b >>>= Long.numberOfTrailingZeros(b);
        }
        
        return a<<Math.min(ashift, bshift);
    }

    
    void run() throws Exception
    {
        is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
        out = new PrintWriter(System.out);
        
        long s = System.currentTimeMillis();
        solve();
        out.flush();
        if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
    }
    
    public static void main(String[] args) throws Exception { 
     new C2().run(); }
    
    private byte[] inbuf = new byte[1024];
    public int lenbuf = 0, ptrbuf = 0;
    
    private int readByte()
    {
        if(lenbuf == -1)throw new InputMismatchException();
        if(ptrbuf >= lenbuf){
            ptrbuf = 0;
            try { lenbuf = is.read(inbuf); } 
            catch (IOException e) { 
              throw new InputMismatchException(); }
            if(lenbuf <= 0)return -1;
        }
        return inbuf[ptrbuf++];
    }
    
    private boolean isSpaceChar(int c) { 
    return !(c >= 33 && c <= 126); }
    private int skip() { 
    int b; while((b = readByte()) != -1 && isSpaceChar(b)); 
    return b; }
    
    private double nd() { return Double.parseDouble(ns()); }
    private char nc() { return (char)skip(); }
    
    private String ns()
    {
        int b = skip();
        StringBuilder sb = new StringBuilder();
        while(!(isSpaceChar(b))){
        // when nextLine, (isSpaceChar(b) && b != ' ')
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
    
    private char[] ns(int n)
    {
        char[] buf = new char[n];
        int b = skip(), p = 0;
        while(p < n && !(isSpaceChar(b))){
            buf[p++] = (char)b;
            b = readByte();
        }
        return n == p ? buf : Arrays.copyOf(buf, p);
    }
    
    private char[][] nm(int n, int m)
    {
        char[][] map = new char[n][];
        for(int i = 0;i < n;i++)map[i] = ns(m);
        return map;
    }
    
    private int[] na(int n)
    {
        int[] a = new int[n];
        for(int i = 0;i < n;i++)a[i] = ni();
        return a;
    }
    
    private int ni()
    {
        int num = 0, b;
        boolean minus = false;
        while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
        if(b == '-'){
            minus = true;
            b = readByte();
        }
        
        while(true){
            if(b >= '0' && b <= '9'){
                num = num * 10 + (b - '0');
            }else{
                return minus ? -num : num;
            }
            b = readByte();
        }
    }
    
    private long nl()
    {
        long num = 0;
        int b;
        boolean minus = false;
        while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
        if(b == '-'){
            minus = true;
            b = readByte();
        }
        
        while(true){
            if(b >= '0' && b <= '9'){
                num = num * 10 + (b - '0');
            }else{
                return minus ? -num : num;
            }
            b = readByte();
        }
    }
    
    private static void tr(Object... o) {
    System.out.println(Arrays.deepToString(o)); }
}

GCD Matrix Python Solution

#!/bin/python3

import math
import os
import random
import re
import sys

def f(k):
    if gf[k]>=0:
        return gf[k]
    res=ga[k]*gb[k]
    if res==0:
        gf[k]=0
        return 0
    for i in range(k+k,m+1,k):
        res-=f(i)
    gf[k]=res
    return res

if __name__ == '__main__':
    nmq = input().split()

    n = int(nmq[0])

    m = int(nmq[1])

    q = int(nmq[2])

    a = list(map(int, input().rstrip().split()))

    b = list(map(int, input().rstrip().split()))

    for q_itr in range(q):
        r1C1R2C2 = input().split()

        r1 = int(r1C1R2C2[0])

        c1 = int(r1C1R2C2[1])

        r2 = int(r1C1R2C2[2])

        c2 = int(r1C1R2C2[3])

        # Write Your Code Here
        sa=set(a[r1:r2+1])
        sb=set(b[c1:c2+1])
        na=len(a)
        nb=len(b)
        mxa=max(sa)
        mxb=max(sb)
        m=min(mxa,mxb)
        mm=max(mxa,mxb)

        ga=[0]*(m+1)
        gb=[0]*(m+1)
        ga[1]=na
        gb[1]=nb

        for i in range(2,m+1):
            for j in range(i,mm+1,i):
                if j in sa:
                    ga[i]+=1
                if j in sb:
                    gb[i]+=1
        gf=[-1]*(m+1)

        f(1)
        r=sum([(x>0) for x in gf])
        print(r)
c, C#, C++, HackerRank Solutions, java, python Tags:C, cpp, CSharp, Hackerrank Solutions, java, python

Post navigation

Previous Post: HackerRank Covering the stains Problem Solution
Next Post: HackerRank Fairy Chess Problem Solution

Related Posts

HackerRank Alien Languages Problem Solution HackerRank Alien Languages Problem Solution c
HackerRank Flipping the Matrix Problem Solution HackerRank Flipping the Matrix Problem Solution c
HackerRank Connected Cells in a Grid Problem Solution HackerRank Connected Cells in a Grid Solution c
HackerRank Angry Professor Problem Solution HackerRank Angry Professor Problem Solution c
HackerRank Minimum Absolute Difference in an Array Problem Solution HackerRank Minimum Absolute Difference in an Array c
HackerRank Best spot Problem Solution HackerRank Best spot Problem Solution c

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

Pick Your Subject
Human Values

Copyright © 2023 TheCScience.

Powered by PressBook Grid Blogs theme