Hackerrank "Sherlock Holmes" challenge

Watson gives to Sherlock an array: A1, A2, ⋯, AN. He also gives to
Sherlock two other arrays: B1, B2, ⋯, BM and C1, C2, ⋯, CM. Then Watson 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

Can you help Sherlock and tell him the resulting array A? You should print all the array elements modulo (1000000007).

Input Format


The first line contains two integer numbers N and M. The
next line contains N integers, the elements of array A. The next two
lines contains M integers each, the elements of array B and C.

Output Format


Print N integers, the elements of array A after
performing the program modulo (1000000007).

Sample Input

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

Sample Output

13 754 2769 1508

If we brute force, it will time out. Please suggest ways on making this efficient.

```
import java.math.BigInteger;
import java.util.Scanner;
import java.util.StringTokenizer;

public class SherlockArray {

public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String line1 = in.nextLine();
StringTokenizer st = new StringTokenizer(line1, " ");

int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
Long[] b = new Long[m];

String strA = in.nextLine();
String[] stA = strA.split(" ");
BigInteger aBI[] = new BigInteger[n];
for (int ia = 0; ia < stA.length; ia++) {
aBI[ia] = new BigInteger(stA[ia]);
}

String strB = in.nextLine();
String[] stB = strB.split(" ");
for (int ib = 0; ib < stB.length; ib++) {
b[ib] = Long.parseLong(stB[ib]);
}

String strC = in.nextLine();
String[] st3 = strC.split(" ");
for (int ic = 0; ic < m; ic++) {
for (int index = b[ic].intValue(); index <= n; index += b[ic]
.intValue()) {
aBI[index - 1] = a

In 1801, a guy called Carl Friedrich Gauss studied problems where the number line wrapped around, called Modular Arithmetic.

In his studies, he proved that:

$$
(a \times b)\ \%\ n = [(a)\ \%\ n \times (b)\ \%\ n]\ \%\ n
$$

Also, 1000000007 is a prime number which means that there are other benefits...

And, it is also just less than half of Integer.MAX_VALUE.

Finally, two int values, no matter how large, when multiplied, will never be larger than Long.MAX_VALUE

Putting this all together, you can rewrite your code without the BigInteger math, something like:

for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
        if (j % B[i] == 0) {
            A[j] = (int)( ( (long) A[j] * C[i]) % 1000000007L);
        }
    }
}
System.out.println(Arrays.toString(A));

So, using some math, you can avoid the BigInteger problem entirely, and keep things as long and int values.

I imagine that this will be enough of a performance improvement to avoid the timeout.

Note, that for large numbers, BigInteger has \$O(s)\$ type complexity where s is the magnitude of the number, when doing multiplication. The bigger the number, the slower the product. Thus, your complexity for your current solution is \$O(nms)\$ where n is the size of the A array, m is the size of the B and C arrays, and s is the average size of the BigIntegers used. By reducing the problem to int-size values, we reduce the time complexity by a full order to just\$O(nm)\$.

There are likely ways for you to be able to solve the math in O(n) time as well.... I just need to think about how to restructure the if condition in the loops

StackExchange Code Review Q#61060, answer score: 15