Soluție HackerRank pentru Sherlock and Queries, subdomeniul Algebra, în Java 8. Include cerința formatată, exemple, explicația pașilor și cod sursă.

  • Problemă: Sherlock and Queries
  • Domeniu: Algebra
  • Limbaj: Java 8

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

Cerință

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 ≤ N, M ≤ 10^5
1 ≤ B[i] ≤ N
1 ≤ A[i], C[i] ≤ 10^5

Sample Input

4 3
1 2 3 4
1 2 3
13 29 71

Sample Output

13 754 2769 1508

Cod sursă

//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;
    }
}
HackerRank Algebra – Sherlock and Queries