Table of Contents
GCD Matrix – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Solutions of Algorithms Data Structures Hard HackerRank:
Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
C++ GCD Matrix HackerRank Solution
#define _CRT_SECURE_NO_WARNINGS
#pragma comment(linker, "/stack:16777216")
#include <string>
#include <vector>
#include <map>
#include <list>
#include <iterator>
#include <set>
#include <queue>
#include <iostream>
#include <sstream>
#include <stack>
#include <deque>
#include <cmath>
#include <memory.h>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <utility>
#include <assert.h>
#include <time.h>
#include <complex.h>
#include <fstream>
#include <sys/stat.h>
#include <stdlib.h>
#include <stdio.h>
using namespace std;
#define FOR(i, a, b) for(int i=(a);i<(b);i++)
#define RFOR(i, b, a) for(int i=(b)-1;i>=(a);--i)
#define FILL(A,value) memset(A,value,sizeof(A))
#define ALL(V) V.begin(), V.end()
#define SZ(V) (int)V.size()
#define PB push_back
#define MP make_pair
#define Pi 3.14159265358979
typedef long long Int;
typedef unsigned long long UInt;
typedef vector<int> VI;
typedef pair<Int, Int> PII;
const int INF = 1000000000;
const int MAX = 100007;
const int MAXD = 20;
const int MOD = 1000000007;
int a[MAX];
int b[MAX];
int ca[MAX];
int cb[MAX];
Int A[MAX];
int main()
{
//freopen("in.txt" , "r" , stdin);
//freopen("out.txt" , "w" , stdout);
int n , m;
cin >> n >> m;
int q;
cin >> q;
FOR(i,0,n) cin >> a[i];
FOR(i,0,m) cin >> b[i];
FOR(i,0,q)
{
int r1,c1,r2,c2;
cin >> r1 >> c1 >> r2 >> c2;
FILL(ca , 0);
FILL(cb , 0);
FOR(i,r1,r2 + 1)
ca[a[i]] ++;
FOR(i,c1,c2 + 1)
cb[b[i]] ++;
FILL(A, 0);
FOR(i,1,MAX)
{
int cntA = 0;
int cntB = 0;
for(int j = i; j < MAX; j += i)
{
cntA += ca[j];
cntB += cb[j];
}
A[i] = 1LL * cntA * cntB;
}
int res = 0;
RFOR(i,MAX,1)
{
for(int j = 2 * i; j < MAX; j += i)
A[i] -= A[j];
if (A[i]) ++ res;
}
cout << res << endl;
}
return 0;
}
Java GCD Matrix HackerRank 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)); }
}
Python 3 GCD Matrix HackerRank Solution
#!/bin/python3
import math
import os
import random
import re
import sys
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()))
def ff(x):
sd = [i for i in range(1, 1 + math.floor(math.sqrt(x))) if x % i == 0]
return set(sd + [int(x / d) for d in sd])
md = {}
for x in set(a).union(set(b)):
md[x] = ff(x)
ar = {}
for i, v in enumerate(a):
for d in md[v]:
if d in ar:
ar[d].add(i)
else:
ar[d] = set()
ar[d].add(i)
br = {}
for j, v in enumerate(b):
for d in md[v]:
if d in br:
br[d].add(j)
else:
br[d] = set()
br[d].add(j)
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])
aps = set()
for i in range(r1, r2 + 1):
aps.update(md[a[i]])
bps = set()
for j in range(c1, c2 + 1):
bps.update(md[b[j]])
ps = aps.intersection(bps)
def rowFindGCD(i, x):
for j in br[x]:
if c1 <= j and j <= c2:
if math.gcd(a[i], b[j]) == x:
return j
return None
def findGCD(x):
for i in ar[x]:
if r1 <= i and i <= r2:
j = rowFindGCD(i, x)
if not (j is None):
return (i, j)
return None
ret = 0
for x in ps:
ret += 1 if findGCD(x) else 0
print(ret)
Python 2 GCD Matrix HackerRank Solution
#!/bin/python
import sys
from fractions import gcd
n,m,q = raw_input().strip().split(' ')
n,m,q = [int(n),int(m),int(q)]
a = map(int, raw_input().strip().split(' '))
b = map(int, raw_input().strip().split(' '))
M = []
for i in xrange(n):
M.append([0]*m)
for j in xrange(m):
M[i][j] = gcd(a[i],b[j])
for a0 in xrange(q):
r1,c1,r2,c2 = raw_input().strip().split(' ')
r1,c1,r2,c2 = [int(r1),int(c1),int(r2),int(c2)]
nums = {}
for i in range(r1,r2+1):
for j in range(c1,c2+1):
x = M[i][j]
if x in nums:
nums[x] += 1
else:
nums[x] = 1
print len(nums)
C GCD Matrix HackerRank Solution
#include <assert.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char* readline();
char** split_string(char*);
int gcd(int a, int b);
struct myset {
int *data;
int size;
int nelem;
};
void myset_init(struct myset *s, int sz);
void myset_insert(struct myset *s, int val);
void myset_free(struct myset *s);
#define myset_nelem(s) ((s)->nelem)
#define MAXSZ ((int) (1e5 + 5))
int acal[MAXSZ], bcal[MAXSZ];
long long dcal[MAXSZ];
int main()
{
char** nmq = split_string(readline());
char* n_endptr;
char* n_str = nmq[0];
int n = strtol(n_str, &n_endptr, 10);
if (n_endptr == n_str || *n_endptr != '\0') { exit(EXIT_FAILURE); }
char* m_endptr;
char* m_str = nmq[1];
int m = strtol(m_str, &m_endptr, 10);
if (m_endptr == m_str || *m_endptr != '\0') { exit(EXIT_FAILURE); }
char* q_endptr;
char* q_str = nmq[2];
int q = strtol(q_str, &q_endptr, 10);
if (q_endptr == q_str || *q_endptr != '\0') { exit(EXIT_FAILURE); }
char** a_temp = split_string(readline());
int* a = malloc(n * sizeof(int));
for (int i = 0; i < n; i++) {
char* a_item_endptr;
char* a_item_str = *(a_temp + i);
int a_item = strtol(a_item_str, &a_item_endptr, 10);
if (a_item_endptr == a_item_str || *a_item_endptr != '\0') { exit(EXIT_FAILURE); }
*(a + i) = a_item;
}
char** b_temp = split_string(readline());
int* b = malloc(m * sizeof(int));
for (int i = 0; i < m; i++) {
char* b_item_endptr;
char* b_item_str = *(b_temp + i);
int b_item = strtol(b_item_str, &b_item_endptr, 10);
if (b_item_endptr == b_item_str || *b_item_endptr != '\0') { exit(EXIT_FAILURE); }
*(b + i) = b_item;
}
// int **M = (int **) malloc(sizeof(int *) * n);
// for (int i=0; i<n; i++)
// M[i] = (int *) calloc(sizeof(int), m);
//
//
// for (int i=0; i<n; i++) {
// for (int j=0; j < m; j++) {
// M[i][j] = gcd_recursive(a[i], b[j]);
// }
// }
for (int q_itr = 0; q_itr < q; q_itr++) {
char** r1C1R2C2 = split_string(readline());
char* r1_endptr;
char* r1_str = r1C1R2C2[0];
int r1 = strtol(r1_str, &r1_endptr, 10);
if (r1_endptr == r1_str || *r1_endptr != '\0') { exit(EXIT_FAILURE); }
char* c1_endptr;
char* c1_str = r1C1R2C2[1];
int c1 = strtol(c1_str, &c1_endptr, 10);
if (c1_endptr == c1_str || *c1_endptr != '\0') { exit(EXIT_FAILURE); }
char* r2_endptr;
char* r2_str = r1C1R2C2[2];
int r2 = strtol(r2_str, &r2_endptr, 10);
if (r2_endptr == r2_str || *r2_endptr != '\0') { exit(EXIT_FAILURE); }
char* c2_endptr;
char* c2_str = r1C1R2C2[3];
int c2 = strtol(c2_str, &c2_endptr, 10);
if (c2_endptr == c2_str || *c2_endptr != '\0') { exit(EXIT_FAILURE); }
{
int maxn = MAXSZ;
int i, w, x, y, z;
w = r1;
x = c1;
y = r2;
z = c2;
//cin >> w >> x >> y >> z;
//w++; x++; y++; z++;
for (i=0; i<maxn; i++) {
acal[i] = bcal[i] = dcal[i] = 0;
}
//fr(i, w, y) a[A[i]] ++;
for (i=w; i <= y; i++) {
acal[a[i]]++;
}
//fr(i, x, z) b[B[i]] ++;
for (i=x; i<=z; i++) {
bcal[b[i]]++;
}
//fr(i, 1, maxn-5) {
for (i = 1; i <= maxn-5; i++) {
int j = i, v1 = 0, v2 = 0;
while( j <= maxn-5 ) {
v1 += acal[j];
v2 += bcal[j];
j += i;
}
acal[i] = v1; bcal[i] = v2;
}
int cnt = 0;
//fb(i, maxn-5, 1) {
for (i=maxn-5; i>=1; i--) {
int j = i;
long long ans = 0;
ans = 1LL * acal[i] * bcal[i];
while(j <= maxn-5) {
ans -= dcal[j];
j += i;
}
dcal[i] = ans;
if( dcal[i] ) cnt ++;
}
printf("%d\n", cnt);
}
}
return 0;
}
void myset_init(struct myset *s, int sz) {
s->data = (int *) malloc(sizeof(int) * sz);
for (int i=0; i<sz; i++) {
s->data[i] = -1;
}
s->nelem = 0;
s->size = sz;
}
void myset_free(struct myset *s) {
free(s->data);
s->nelem = 0;
s->size = 0;
}
int myset_contains(struct myset *s, int val)
{
for (int i=0; i<=s->size; i++) {
int data = s->data[i];
if (data < 0) {
return 0;
}
if (data == val) {
return 1;
}
}
return 0;
}
void myset_append(struct myset *s, int val)
{
int i = 0;
while (s->data[i] > 0 && i < s->size)
i++;
s->data[i] = val;
s->nelem++;
}
void myset_insert(struct myset *s, int val) {
if (!myset_contains(s, val))
myset_append(s, val);
}
int gcd(int a, int b)
{
int temp;
while (b != 0) {
temp = b;
b = a % b;
a = temp;
}
return a;
}
char* readline() {
size_t alloc_length = 1024;
size_t data_length = 0;
char* data = malloc(alloc_length);
while (true) {
char* cursor = data + data_length;
char* line = fgets(cursor, alloc_length - data_length, stdin);
if (!line) { break; }
data_length += strlen(cursor);
if (data_length < alloc_length - 1 || data[data_length - 1] == '\n') { break; }
size_t new_length = alloc_length << 1;
data = realloc(data, new_length);
if (!data) { break; }
alloc_length = new_length;
}
if (data[data_length - 1] == '\n') {
data[data_length - 1] = '\0';
}
data = realloc(data, data_length);
return data;
}
char** split_string(char* str) {
char** splits = NULL;
char* token = strtok(str, " ");
int spaces = 0;
while (token) {
splits = realloc(splits, sizeof(char*) * ++spaces);
if (!splits) {
return splits;
}
splits[spaces - 1] = token;
token = strtok(NULL, " ");
}
return splits;
}
Warmup
Implementation
Strings
Sorting
Search
Graph Theory
Greedy
Dynamic Programming
Constructive Algorithms
Bit Manipulation
Recursion
Game Theory
NP Complete
Debugging
Leave a comment below
