# 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] = aBI[index - 1].multiply(new BigInteger(st3[ic]));
}
}

for (int ia = 0; ia < n; ia++) {
aBI[ia] = aBI[ia].mod(new BigInteger("1000000007"));
System.out.print(aBI[ia] + " ");
}

}

}

-

A far more optimal solution involves keeping track of the number of times that B[i] occurs.

This is because for every multiple of B[i]: B[i], 2 * B[i], ..., j * B[i], we multiply A[i * j] by C[i]

This yields the following info for the example:

1 occurs 4 times (4 multiples), 2 occurs 2 times (2 multiples), 3 occurs 1 time (3 multiples), 4 occurs 1 time (1 multiple)

Therefore, we multiply 1 by 13, 2 by 13, 3 by 13, 4 by 13 (first 4 multiples of 1)

we multiply 2 by 29, 4 by 29 (first 2 multiples of 2)

we multiply 3 by 71 (first multiple of 3)

we multiply 4 by 1 (since C[4] doesn't exist)

This yields a net result of multiplying 1 by 13, 2 by 13 * 29, 3 by 13 * 71, 4 by 13 * 29

This approach ends up being $O(N * log(N))$ because for each N, you do N/i multiplications, meaning you do a total of:

N/1 + N/2 + N/3 + N/4 + ... N/N = N * (1/1 + 1/2 + 1/3 + ... + 1/N) = O(Nlog(N)),


since (1/1 + 1/2 + 1/3 + ...) is the harmonic series and grows with $O(log(N))$

Here is the relevant code, which produced the results in under 2 seconds, mostly due to very inefficient I/O. I changed BigIntegers to Longs, as BigIntegers are very SLOW in Java. I also repeatedly used modulo multiplication. These two suggestions were brought up by rofl, but I wanted to re-iterate them.

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

public class Solution {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
Long N = scanner.nextLong();
Long M = scanner.nextLong();
scanner.nextLine();

ArrayList<Long> A = new ArrayList<Long>();
ArrayList<Long> B = new ArrayList<Long>();
ArrayList<Long> C = new ArrayList<Long>();

for (String string : scanner.nextLine().split(" ")) {
}
for (String string : scanner.nextLine().split(" ")) {
}
for (String string : scanner.nextLine().split(" ")) {
}

HashMap<Long, Long> counts = new HashMap<Long, Long>();

for (int i = 1; i < M+1; i++) {
if (counts.containsKey(B.get(i))) {
counts.put(B.get(i), (counts.get(B.get(i)) * C.get(i)) % 1000000007L);
}
else {
counts.put(B.get(i), C.get(i));
}
}

for (Long i = 1L; i < N+1; i++) {
for (Long j = 1L; j < (N / i) + 1L; j++) {
if (counts.containsKey(i)) {
A.set((int)(i * j), (A.get((int)(i * j)) * counts.get(i)) % 1000000007L);
}
}
}

System.out.print(A.get(1));
for (int i = 2; i < A.size(); i++) {
System.out.print(" " + A.get(i));
}
}
}

-
Thank you very much @mleyfman for the effort on code as well.. It made things clear for me.. This was my first post and got a wonderful support! Thanks again all! :) –  Sharath Aug 27 '14 at 6:16

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

-
Thank you for the quick turn around @rolfl –  Sharath Aug 27 '14 at 6:17

The original post used 1-based arrays. If you change them to 0-based, you should test (j+1)%B[i] == 0, not j%B[i] == 0.

for (int j = 0; j < M; j++) {
if ((j+1) % B[i] == 0) {
...
}
}


And that can be rewritten:

for (int j = B[i]-1; j < M; j+=B[i]) {
...
}


It can be faster depending how large the B[i] are.

-
You should still start with int j = 0. And it is faster even with B[i]==1 (avoids a division) –  Hagen von Eitzen Aug 26 '14 at 19:00
Oops, indeed!. Fixed. Er... But the original code starts the loops with 1. So it is wrong either way. –  Florian F Aug 26 '14 at 23:30
Fixed again to adjust for 0-based arrays. –  Florian F Aug 26 '14 at 23:40
Thank you @FlorianF –  Sharath Aug 27 '14 at 6:17

• using modular (long) integer arithmetic (rolfl)
• speeding up the inner loop by predicting the outcome of the if (Florian F)

A third possible speedup consists of grouping equal $B$ values together. If the same value $B_i$ occurs $k$ times, you can handle them all together with $k - 1 + \frac{M}{B}$ modular multiplications instead of $\frac{kM}{B}$.

Using these three optimizations my worst test case took 0.19s, and I didn't even make use of another general optimization (for HackerRank and similar competitions) — namely to make sure that my I/O is fast even for large input.

-
Hagen, was that k - 1 + M/B or (k - 1 + M)/B? Your use of parentheses kind of confused me... –  Schism Aug 26 '14 at 19:29
Thank you @Hagen von Eitzen –  Sharath Aug 27 '14 at 6:16