Hackerrank "Sherlock Holmes" challenge

Question

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] + " ");
    }

}


}

Answer 1

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>();

       A.add(0L);
       for (String string : scanner.nextLine().split(" ")) {
           A.add(new Long(string));
       }
       B.add(0L);
       for (String string : scanner.nextLine().split(" ")) {
           B.add(new Long(string));
       }
       C.add(0L);
       for (String string : scanner.nextLine().split(" ")) {
           C.add(new Long(string));
       }

       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));
       }
    } 
}

Answer 2

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

Answer 3

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.

Answer 4

Other answers already deal with

• 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.