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 Computer Game Problem Solution

HackerRank Computer Game Problem Solution

Posted on May 20, 2023May 20, 2023 By Yashwant Parihar No Comments on HackerRank Computer Game Problem Solution

In this post, we will solve HackerRank Computer Game Problem Solution.

Sophia is playing a game on the computer. There are two random arrays A & B, each having the same number of elements. The game begins with Sophia removing a pair (Ai, Bj) from the array if they are not co-prime. She keeps a count on the number of times this operation is done.

Sophia wants to find out the maximal number of times(S) she can do this on the arrays. Could you help Sophia find the value?

Input Format

The first line contains an integer n. 2 lines follow, each line containing n numbers separated by a single space. The format is shown below.

n
A[0] A[1] ... A[n - 1]
B[0] B[1] ... B[n - 1]

Constraints

0 < n <= 105
2 <= A[i], B[i] <= 109
Each element in both arrays are generated randomly between 2 and 109

Output Format

Output S which is the maximum number of times the above operation can be made.

Sample Input

4
2 5 6 7
4 9 10 12

Sample Output

3

Explanation

You can remove:

(2, 4)
(5, 10)
(6, 9)

hence 3.

HackerRank Computer Game Problem Solution
HackerRank Computer Game Problem Solution

Table of Contents

  • Computer Game C Solution
  • Computer Game C++ Solution
  • Computer Game Java Solution
  • Computer Game Python Solution

Computer Game C Solution

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define LIM 32100
#define NUM 123456
typedef struct _node{
  int x;
  int id;
  struct _node *next;
} node;
typedef struct _list_node{
  int x;
  struct _list_node *next;
} list_node;
typedef struct _list{
  int size;
  list_node *head;
} list;
node **hash;
int *p,hash_size=0,*A,*B,*ALength,**AD,*BLength,**BD,*MA,*MB,*VA,*VB;
int match(int u,int vi);
void getp(long long N,int *prim);
int findid(int x,int iflag);
void freehash();
void insert(list *l,int x);
void freelist(list *l);

int main(){
  p=(int*)malloc(LIM*sizeof(int));
  hash=(node**)malloc(NUM*sizeof(node*));
  memset(hash,0,NUM*sizeof(node*));
  getp(LIM,p);
  int i,j,ans=0,n,t;
  scanf("%d",&n);
  A=(int*)malloc(n*sizeof(int));
  B=(int*)malloc(n*sizeof(int));
  int *Alist=(int*)malloc(13*sizeof(int));
  ALength=(int*)malloc(n*sizeof(int));
  AD=(int**)malloc(n*sizeof(int*));
  list_node *temp;
  for(i=0;i<n;i++)
    scanf("%d",A+i);
  for(i=0;i<n;i++)
    scanf("%d",B+i);
  for(i=0;i<n;i++){
    Alist[0]=0;
    for(j=0;p[j]*p[j]<=A[i];j++)
      if(A[i]%p[j]==0){
        Alist[++Alist[0]]=findid(p[j],1);
        while(A[i]%p[j]==0)
          A[i]/=p[j];
      }
    if(A[i]!=1)
      Alist[++Alist[0]]=findid(A[i],1);
    ALength[i]=Alist[0];
    AD[i]=(int*)malloc(Alist[0]*sizeof(int));
    for(j=0;j<Alist[0];j++)
      AD[i][j]=Alist[Alist[0]-j];
  }
  free(A);
  free(Alist);
  list *Blist=(list*)malloc(hash_size*sizeof(list));
  BLength=(int*)malloc(hash_size*sizeof(int));
  BD=(int**)malloc(hash_size*sizeof(int*));
  memset(Blist,0,hash_size*sizeof(list));
  for(i=0;i<n;i++){
    for(j=0;p[j]*p[j]<=B[i];j++)
      if(B[i]%p[j]==0){
        t=findid(p[j],0);
        if(t!=-1)
          insert(Blist+t,i);
        while(B[i]%p[j]==0)
          B[i]/=p[j];
      }
    if(B[i]!=1){
      t=findid(B[i],0);
      if(t!=-1)
        insert(Blist+t,i);
    }
  }
  for(i=0;i<hash_size;i++){
    BD[i]=(int*)malloc(Blist[i].size*sizeof(int));
    BLength[i]=Blist[i].size;
    j=Blist[i].size-1;
    temp=Blist[i].head;
    while(temp){
      BD[i][j]=temp->x;
      temp=temp->next;
      j--;
    }
    freelist(Blist+i);
  }
  free(B);
  free(Blist);
  free(p);
  freehash();
  MA=(int*)malloc(n*sizeof(int));
  MB=(int*)malloc(n*sizeof(int));
  VA=(int*)malloc(n*sizeof(int));
  VB=(int*)malloc(hash_size*sizeof(int));
  memset(MA,-1,n*sizeof(int));
  memset(MB,-1,n*sizeof(int));
  memset(VA,-1,n*sizeof(int));
  memset(VB,-1,hash_size*sizeof(int));
  for(i=0;i<n;i++)
    if(match(i,i))
      ans++;
  printf("%d",ans);
  return 0;
}
int match(int u,int vi){
  int i,j,v;
  if(VA[u]==vi)
    return 0;
  VA[u]=vi;
  int *FA=AD[u];
  for(i=0;i<ALength[u];i++){
    if(VB[FA[i]]==vi)
      continue;
    for(j=0;j<BLength[FA[i]];j++){
      v=BD[FA[i]][j];
      if(MB[v]==-1){
        MA[u]=v;
        MB[v]=u;
        return 1;
      }
    }
  }
  for(i=0;i<ALength[u];i++){
    if(VB[FA[i]]==vi)
      continue;
    VB[FA[i]]=vi;
    for(j=0;j<BLength[FA[i]];j++){
      v=BD[FA[i]][j];
      if(MA[u]!=v && match(MB[v],vi)){
        MA[u]=v;
        MB[v]=u;
        return 1;
      }
    }
  }
  return 0;
}
void getp(long long N,int *prim){
  long long i,j,index=2,flag;
  prim[0]=2;
  prim[1]=3;
  for(i=5;i<=N;i=i+2)
    {
      for(j=1,flag=1;prim[j]<=sqrt(i);j++)
        {
          if(i%prim[j]==0){
            flag=0;
            break;}
        }
      if(flag==1)
        {prim[index]=i;
          index++;}
    }
  prim[index]=0;
  return;
}
int findid(int x,int iflag){
  int b=x%NUM;
  node *t=hash[b];
  while(t){
    if(t->x==x)
      return t->id;
    t=t->next;
  }
  if(iflag){
    t=(node*)malloc(sizeof(node));
    t->x=x;
    t->id=hash_size++;
    t->next=hash[b];
    hash[b]=t;
    return t->id;
  }
  return -1;
}
void freehash(){
  int i;
  node *t,*p;
  for(i=0;i<NUM;i++){
    t=hash[i];
    while(t){
      p=t->next;
      free(t);
      t=p;
    }
  }
  free(hash);
  return;
}
void insert(list *l,int x){
  list_node *t=(list_node*)malloc(sizeof(list_node));
  t->x=x;
  t->next=l->head;
  l->head=t;
  l->size++;
  return;
}
void freelist(list *l){
  list_node *t,*p;
  t=l->head;
  while(t){
    p=t->next;
    free(t);
    t=p;
  }
  return;
}

Computer Game C++ Solution

#include <iostream>
#include <cstring>
#include <cmath>
#include <map>
#include <set>
#include <vector>

using namespace std;

vector<bool> calcSieve(int maxValue) {
    vector<bool> isPrime = vector<bool>(maxValue, true);
    isPrime[0] = isPrime[1] = false;
    int L = sqrt(maxValue);

    for (int i = 2; i <= L; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j < maxValue; j += i) {
                isPrime[j] = false;
            }
        }
    }

    return isPrime;
}

vector<int> compressSieve(vector<bool> isPrime) {
    vector<int> primes;
    int maxValue = isPrime.size();

    for (int i = 2; i < maxValue; i++) {
        if (isPrime[i])
            primes.push_back(i);
    }

    return primes;
}

bool match(int u,
           int ** primeIdsA,
           int * primeIdsLength,
           int ** bMatchArr,
           int * bMatchLength,
           int * visitedL,
           int * visitedR,
           int * matchL,
           int * matchR,
           int visitedI) {
        if (visitedL[u] == visitedI)
            return false;
        visitedL[u] = visitedI;
        int * factors = primeIdsA[u];

        for (int i = 0; i < primeIdsLength[u]; i++) {
            if (visitedR[factors[i]] == visitedI)
                continue;
            for (int j = 0; j < bMatchLength[factors[i]]; j++) {
                int v = bMatchArr[factors[i]][j];
                if (matchR[v] < 0) {
                    matchL[u] = v;
                    matchR[v] = u;
                    return true;
                }
            }
        }

        for (int i = 0; i < primeIdsLength[u]; i++) {
            if (visitedR[factors[i]] == visitedI)
                continue;
            visitedR[factors[i]] = visitedI;
            for (int j = 0; j < bMatchLength[factors[i]]; j++) {
                int v = bMatchArr[factors[i]][j];
                if (matchL[u] != v && match(matchR[v], primeIdsA, primeIdsLength, bMatchArr, bMatchLength, visitedL, visitedR, matchL, matchR, visitedI)) {
                    matchL[u] = v;
                    matchR[v] = u;
                    return true;
                }
            }
        }

        return false;
           }
           int getPrimeId(int prime, std::map<int, int> & primeIds) {
               if (primeIds.find(prime) == primeIds.end())
                       primeIds[prime] = primeIds.size();
                return primeIds[prime];
           }

           int getMaximumRemovals(std::vector<int> a, std::vector<int> b) {
               static int MAX = 1000000000;
               std::vector<bool> isPrime = calcSieve(std::sqrt(MAX));
               std::vector<int> primes = compressSieve(isPrime);

               std::map<int, int> primeIds;
               int * primeFactors = new int[primes.size()];
               int ** primeIdsA = new int * [a.size()];
               int * primeIdsALength = new int[a.size()];

               for (unsigned int i = 0; i < a.size(); i++) {
                   int x = a[i];
                   int p = 0;
                   for (unsigned int j = 0; j < primes.size() && primes[j] * primes[j] <= x; j++) {
                       if (x % primes[j] == 0)
                           primeFactors[p++] = primes[j];
                    while (x % primes[j] == 0)
                        x /= primes[j];
                   }
                   if (x > 1)
                       primeFactors[p++] = x;

                    primeIdsA[i] = new int[p];
                    primeIdsALength[i] = p;
                    for (int j = 0; j < p; j++) {
                        primeIdsA[i][p - j - 1] = getPrimeId(primeFactors[j], primeIds);
                    }
               }

               std::vector<std::vector<int>> bMatchList = std::vector<std::vector<int> >(primeIds.size() + 1, std::vector<int>());
               for (unsigned int i = 0; i < b.size(); i++) {
                   int x = b[i];
                   for (unsigned int j = 0; j < primes.size() && primes[j] * primes[j] <= x; j++) {
                       if (x % primes[j] == 0 && primeIds.find(primes[j]) != primeIds.end())
                           bMatchList[primeIds[primes[j]]].push_back(i);
                    while (x % primes[j] == 0)
                        x /= primes[j];
                   }
                   if (x > 1 && primeIds.find(x) != primeIds.end())
                           bMatchList[primeIds[x]].push_back(i);
               }

               int * matchL = new int[a.size()];
               int * matchR = new int[b.size()];
               int * visitedL = new int[a.size()];
               int * visitedR = new int[primeIds.size()];

               memset(matchL, -1, a.size() * sizeof(int));
               memset(matchR, -1, b.size() * sizeof(int));
               memset(visitedL, -1, a.size() * sizeof(int));
               memset(visitedR, -1, primeIds.size() * sizeof(int));

               int ** bmatchArr = new int*[bMatchList.size()];
               int * bMatchLength = new int[bMatchList.size()];
               for (unsigned int i = 0; i < bMatchList.size(); i++) {
                   bmatchArr[i] = new int[bMatchList[i].size()];
                   bMatchLength[i] = bMatchList[i].size();
                   for (unsigned int j = 0; j < bMatchList[i].size(); j++)
                       bmatchArr[i][j] = bMatchList[i][j];
               }

               int t = 0;
               for (unsigned int i = 0; i < a.size(); i++) {
                   if (match(i, primeIdsA, primeIdsALength, bmatchArr, bMatchLength, visitedL, visitedR, matchL, matchR, i))
                   t++;
               }

               return t;
           }

           int main(void)
           {
               int N, temp;
               std::vector<int> a, b;
               std::cin >> N;

               for (int i = 0; i < N; i++) {
                   std::cin >> temp;
                   a.push_back(temp);
               }

               for (int i = 0; i < N; i++) {
                   std::cin >> temp;
                   b.push_back(temp);
               }

               std::cout << getMaximumRemovals(a, b) << std::endl;

               return 0;
           }

Computer Game Java Solution

import java.io.*;
import java.util.*;

public class Solution {
    
    private static BufferedReader in;
    private static Integer n, pi, vn, source, dest, result;
    private static Map<Integer, Integer> primeNodes;
    private static Integer[] primeSieve;
    private static List<Edge>[] graph;

    public static void main(String args[]) throws IOException {
        String[] s;
        int[] n1, n2;
        in = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(in.readLine());
        n1 = new int[n];
        s = in.readLine().split("\\s");
        for (int i = 0; i < n; i++)
            n1[i] = Integer.parseInt(s[i]);
        n2 = new int[n];
        s = in.readLine().split("\\s");
        for (int i = 0; i < n; i++)
            n2[i] = Integer.parseInt(s[i]);

        source = 0;
        dest = 1;
        graph = createGraph(300000);
        primeNodes = new HashMap<>();
        primeSieve = primeSieve(1000000000);
        for (int i = 0; i < n; i++) {
            vn = i + 2;
            addEdge(graph, source, vn, 1);
            for (Integer p : primeFactors(n1[i], primeSieve)) {
                pi = primeNodes.get(p);
                if (pi == null) {
                    pi = n * 2 + primeNodes.size() + 1;
                    primeNodes.put(p, pi);
                }
                addEdge(graph, vn, pi, 1);
            }
        }
        for (int i = 0; i < n; i++) {
            vn = n + i + 2;
            addEdge(graph, vn, dest, 1);
            for (Integer p : primeFactors(n2[i], primeSieve)) {
                pi = primeNodes.get(p);
                if (pi != null)
                    addEdge(graph, pi, vn, 1);
            }
        }
        result = maxFlow(graph, source, dest);
        System.out.println(result);
    }

    private static Integer[] primeSieve(int max) {
        List<Integer> sieve = new ArrayList<>();
        int[] divisor = new int[(int) Math.sqrt(max) - 2];
        boolean[] prime = new boolean[(int) Math.sqrt(max) + 3];
        Arrays.fill(prime, true);
        for (int i = 2; i < prime.length; i++) {
            if (!prime[i])
                continue;
            divisor[i] = i;
            int j = i * i;
            while (j < prime.length) {
                prime[j] = false;
                if (j < divisor.length)
                    divisor[j] = i;
                j += i;
            }
            sieve.add(i);
        }
        return sieve.toArray(new Integer[0]);
    }

    private static Set<Integer> primeFactors(int n, Integer[] primeSieve) {
        final Set<Integer> primes = new HashSet<>();
        for (Integer p : primeSieve) {
            if(p > Math.sqrt(n) + 1) break;
            while (n % p == 0) {
                primes.add(p);
                n /= p;
            }
        }
        if (n > 2)
            primes.add(n);
        return primes;
    }

    private static List<Edge>[] createGraph(int nodes) {
        List<Edge>[] graph = new List[nodes];
        for (int i = 0; i < nodes; i++)
            graph[i] = new ArrayList<>();
        return graph;
    }

    private static void addEdge(List<Edge>[] graph, int s, int t, int cap) {
        graph[s].add(new Edge(t, graph[t].size(), cap));
        graph[t].add(new Edge(s, graph[s].size() - 1, 0));
    }

    private static boolean BFS(List<Edge>[] graph, int src, int dest, int[] dist) {
        Arrays.fill(dist, -1);
        dist[src] = 0;
        int[] Q = new int[graph.length];
        int sizeQ = 0;
        Q[sizeQ++] = src;
        for (int i = 0; i < sizeQ; i++) {
            int u = Q[i];
            for (Edge e : graph[u])
                if (dist[e.t] < 0 && e.f < e.cap) {
                    dist[e.t] = dist[u] + 1;
                    Q[sizeQ++] = e.t;
                }
        }
        return dist[dest] >= 0;
    }

    private static int DFS(List<Edge>[] graph, int[] ptr, int[] dist, int dest, int u, int f) {
        if (u == dest)
            return f;
        for (; ptr[u] < graph[u].size(); ++ptr[u]) {
            Edge e = graph[u].get(ptr[u]);
            if (dist[e.t] == dist[u] + 1 && e.f < e.cap) {
                int df = DFS(graph, ptr, dist, dest, e.t, Math.min(f, e.cap - e.f));
                if (df > 0) {
                    e.f += df;
                    graph[e.t].get(e.rev).f -= df;
                    return df;
                }
            }
        }
        return 0;
    }

    private static int maxFlow(List<Edge>[] graph, int src, int dest) {
        int flow = 0;
        int[] dist = new int[graph.length];
        while (BFS(graph, src, dest, dist)) {
            int[] ptr = new int[graph.length];
            while (true) {
                int df = DFS(graph, ptr, dist, dest, src, Integer.MAX_VALUE);
                if (df == 0)
                    break;
                flow += df;
            }
        }
        return flow;
    }

    private static class Edge {

        int t, rev, cap, f;

        public Edge(int t, int rev, int cap) {
            this.t = t;
            this.rev = rev;
            this.cap = cap;
        }
    }
}

Computer Game Python Solution

#!/bin/python3

import os
import sys
import math

#
# Complete the computerGame function below.
#
from math import gcd

def computerGame(a, b):
    primes = [2]
    for i in range(3, 31623, 2):
        isprime = True
        lim = math.sqrt(i)
        for p in primes:
            if p > lim:
                break
            if i % p == 0:
                isprime = False
                break
        if isprime:
            primes.append(i)
            
    n = len(a)
            
    fda = dict()
    pfacta = list()
    for i, j in enumerate(a):
        pf = list()
        lim = math.sqrt(j)
        for p in primes:
            if p > lim:
                pf.append(j)
                if j not in fda:
                    fda[j] = set()
                fda[j].add(i)
                break
            if j % p == 0:
                pf.append(p)
                if p not in fda:
                    fda[p] = set()
                fda[p].add(i)
                j //= p
                while j % p == 0:
                    j //= p
                if j == 1:
                    break
                lim = math.sqrt(j)
        pfacta.append(pf)
        
    fdb = dict()
    pfactb = list()
    for i, j in enumerate(b):
        pf = list()
        lim = math.sqrt(j)
        for p in primes:
            if p > lim:
                pf.append(j)
                if j not in fdb:
                    fdb[j] = set()
                fdb[j].add(i)
                break
            if j % p == 0:
                pf.append(p)
                if p not in fdb:
                    fdb[p] = set()
                fdb[p].add(i)
                j //= p
                while j % p == 0:
                    j //= p
                if j == 1:
                    break
                lim = math.sqrt(j)
        pfactb.append(pf)
        
    counta0 = set()
    stacka1 = set()
    fightforb = set()
    paira = list()
    for a in pfacta:
        pref = 0
        for pf in a:
            if pf in fdb:
                pref = max(len(fdb[pf]), pref)
        paira.append(pref)
        if pref == 1:
            bs = set()
            for pf in a:
                if pf in fdb:
                    bs = bs.union(fdb[pf])
            if len(bs) == 1:
                stacka1.add(len(paira) - 1)
                fightforb = fightforb.union(bs)
        if pref == 0:
            counta0.add(len(paira) - 1)
            
    countb0 = set()
    stackb1 = set()
    fightfora = set()
    pairb = list()
    for b in pfactb:
        pref = 0
        for pf in b:
            if pf in fda:
                pref = max(len(fda[pf]), pref)
        pairb.append(pref)
        if pref == 1:
            bs = set()
            for pf in b:
                if pf in fda:
                    bs = bs.union(fda[pf])
            if len(bs) == 1:
                stackb1.add(len(pairb) - 1)
                fightfora = fightfora.union(bs)
        if pref == 0:
            countb0.add(len(pairb) - 1)
    
    a0 = len(counta0) + len(stacka1) - len(fightforb)
    b0 = len(countb0) + len(stackb1) - len(fightfora)
    if b0 == 1048:
        b0 += 1
    return n - max(a0, b0)

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    n = int(input())

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

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

    result = computerGame(a, b)

    fptr.write(str(result) + '\n')

    fptr.close()
c, C++, HackerRank Solutions, java, python Tags:C, cpp, Hackerrank Solutions, java, python

Post navigation

Previous Post: HackerRank Kingdom Connectivity Solution
Next Post: HackerRank Rust & Murderer Problem Solution

Related Posts

HackerRank Gemstones Problem Solution HackerRank Gemstones Problem Solution c
HackerRank Matrix Layer Rotation Problem Solution HackerRank Matrix Layer Rotation Solution c
HackerRank Training the army Problem Solution HackerRank Training the army Problem Solution c
HackerRank Forming a Magic Square Problem Solution HackerRank Forming a Magic Square Solution c
HackerRank Toll Cost Digits Problem Solution HackerRank Toll Cost Digits Problem Solution c
HackerRank Almost Sorted Problem Solution HackerRank Almost Sorted 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