HackerRank Algebra – Sherlock and Queries

Challenge: Sherlock and Queries

Subdomeniu: Algebra (algebra)

Scor cont: 30.0 / 30

Submission status: Accepted

Submission score: 1.0

Submission ID: 464734021

Limbaj: java8

Link challenge: https://www.hackerrank.com/challenges/sherlock-and-queries/problem

Cerinta

Watson gives Sherlock an array $A$ of $N$ elements and two arrays $B$ and $C$, of $M$ elements each. Then he asks Sherlock to perform the following program:

    for i = 1 to M do
        for j = 1 to N do
            if j % B[i] == 0 then
                A[j] = A[j] * C[i]
            endif
        end do
    end do

This code needs to be optimized. Can you help Sherlock and tell him the resulting array $A$? You should print all the array elements modulo $(10^9 + 7)$.
          
**Input Format**     
The first line contains two integer, $N$ and $M$. The next line contains $N$ integers, the elements of array $A$. The last two lines contain $M$ integers each, the elements of array $B$ and $C$, respectively.

**Output Format**     
Print $N$ space-separated integers, the elements of array $A$ after performing the program modulo $(10^9 + 7)$.

**Constraints**  
$1 \le N, M \le 10^5$   
$1 \le B[i] \le N$   
$1 \le A[i], C[i] \le 10^5$

**Sample Input**

	4 3
	1 2 3 4
	1 2 3
	13 29 71
    
**Sample Output**

	13 754 2769 1508

Cod sursa

//https://www.hackerrank.com/challenges/sherlock-and-queries
import java.io.*;
import java.util.*;

public class Solution{
    private final static int MOD = 1000000007;
    public static void main(String[] args) throws IOException{
        //INPUT
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] strs = br.readLine().split(" ");
        int N = Integer.parseInt(strs[0]);
        int M = Integer.parseInt(strs[1]);
        int[] A = getArr(br.readLine().split(" "));
        int[] B = getArr(br.readLine().split(" "));
        int[] C = getArr(br.readLine().split(" "));
        
        //SOLVE
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(int i = 0; i < M; ++i){
            int key = B[i];
            Integer j = map.get(key);
            map.put(key, (j == null) ? C[i] : (int)((((long)j) * C[i]) % MOD));
        }
        
        for(int divisor : map.keySet()){
            long multiplier = map.get(divisor);
            for(int j = divisor - 1; j < N; j += divisor){
                A[j] = (int)((A[j] * multiplier) % MOD);
            }
        }
        
        //OUTPUT
        StringBuffer sb = new StringBuffer();
        for(int i = 0; i < N; ++i){
            sb.append(A[i] + " ");
        }
        System.out.print(sb);
    }
    private static int[] getArr(String[] strs){
        final int N = strs.length;
        int[] arr = new int[N];
        for(int i = 0; i < N; ++i){
            arr[i] = Integer.parseInt(strs[i]);
        }
        return arr;
    }
}