2

In this problem I have a number of queries for which I have to output the count of integers in the array which is divisible by k(one of the queries).The array contains duplicate elements. I am trying to optimise the problem and my approach is given below :

Code:

public static void main(String[] args) {
    Scanner sc=new Scanner(System.in);
     int[] ar={2,4,6,9,11,34,654,23,32,54,76,21432,32543,435,43543,643,2646,4567,457654,75,754,7,567865,8765877,53,2};
     int query=sc.nextInt();
     int length=ar.length;
     int count=0;
     for (int i=0;i<query ;i++ ) {
        int x=sc.nextInt();
        for (int j=0;j<length ;j++ ) {
            if(ar[j]>x){
                if(ar[j]%x==0){
                    count++;
                }
            }
        }
        System.out.println("Count:"+count);
     }
}

The above code gives the correct output, but the complexity is O(query*length) and what if the array size is much bigger,the program will timeout.

Can anyone help me optimize the problem?

Pritom Mazumdar
  • 325
  • 5
  • 20
  • You could separate your `ar` array into three smaller arrays: One with primes, one with small non-primes and one with large non-primes. For the primes, you don't have to check a modulo remainder. A number which is equal to a prime cannot be equal to another prime. Depending on the size of `x`, you can skip the small array numbers. – Axel Kemper Sep 24 '17 at 08:58
  • is this a problem from any coding platform like hackerank or leetcode? If yes, can you provide the link for the problem to verify the test cases? – CodeHunter Sep 24 '17 at 09:23
  • Ok I will try that – Pritom Mazumdar Sep 24 '17 at 09:24
  • @CodeHunter, it is a problem from the coding platform hackerearth, but it does not show any test case. – Pritom Mazumdar Sep 24 '17 at 09:26
  • What's the maximum length of the array? and what's the maximum value of an element in that array? – Islam Hassan Sep 24 '17 at 10:59
  • @IslamHassan maximum size of the array is `10^5` and maximum value of an element in an array is `10^5' , also the maximum query size is `10^5` – Pritom Mazumdar Sep 24 '17 at 12:19
  • Why do you check `ar[j]>x`? If ar[j] is 0 or x it also divisible by x. – Henry Sep 27 '17 at 04:15
  • Ya, my bad for putting `ar[j]>x`. But still if I don't use `ar[j]>x` , it doesn't get optimised – Pritom Mazumdar Sep 27 '17 at 05:01

3 Answers3

1

One optimization that you could do is to take advantage of short-circuiting, and use one if statement (instead of two).

So change this:

if(ar[j]>x) {
  if(ar[j]%x==0) {

to this:

if(ar[j]>x && ar[j]%x==0) {

This will not affect the time complexity of your algorithm, but it will help Branch Prediction.

gsamaras
  • 71,951
  • 46
  • 188
  • 305
1

and maximum value of an element in an array is 10^5

This makes it trivial. Use boolean[10001] and mark all multiples of all queries. Then use it for testing the elements.

The new problem is how to mark all the multiples when there are many small queries. The worst case would be queries like {1, 1, 1, ...}, but duplicates can be trivial removed e.g., using a HashSet. Now the worst case is {1, 2, 3, 4, ...}, which needs 10001/1 + 10001/2 + 10001/3... steps. You can do some special treatment for the smallest queries like removing multiples.

For example, when you look at all queries up to 10 and remove multiples among them, then the worst case is {2, 3, 5, 7, 11, 12, 13, 14...}, which should make the marking pretty fast. This step may not be needed at all.

maaartinus
  • 44,714
  • 32
  • 161
  • 320
0

You can do a precomputation step to build a divisors' table. For every element in the array calculate its divisors. You can calculate divisors of a number efficiently in O(sqrt(V)) assuming V is the maximum value in the array. Building the full table will cost O(n * sqrt(V)) which according to your constraints equals 100,000 * sqrt(100,000) =~ 32M which shouldn't be a lot. Memory complexity would be the same.

Then you can answer your queries in O(1) by a lookup in the table.

You can check this link for how to generate divisors in O(sqrt(V)).

Islam Hassan
  • 1,736
  • 4
  • 26
  • 42
  • Okay , I will try that – Pritom Mazumdar Sep 24 '17 at 16:30
  • Can you help me making the divisors table, like what data structure should I use to store the divisors – Pritom Mazumdar Sep 24 '17 at 17:48
  • A hashset should be enough. Whenever you find a number that divides any number in the array insert it into a hashset. Later when you receive a query check that whether it's in the hashset or not. – Islam Hassan Sep 24 '17 at 17:53
  • There is just one problem, if suppose the array contains duplicate values the output of the query won't be correct – Pritom Mazumdar Sep 26 '17 at 05:14
  • I applied your algorithm, and instead of `hashset` I used an `arraylist` since the array can contain duplicate elements but the time limit exceeded. The main problem here is that the `array` contains duplicate elements and even if I were to build a divisors' table for every query I have to get the frequency/count of the query in the `list` and for that the time limit exceeds. – Pritom Mazumdar Sep 26 '17 at 06:06
  • You HAVE TO use a hashset, a lookup in an arraylist will take O(n) which will take long, while a lookup in a hashset takes O(1). It shouldn't matter if you have duplicate divisors or not, you only need to check if a divisor exists or not, you don't care how many times it exists. So instead of doing this check ```ar[j]%x==0```, you'll do ```hashset.contains(x)```. – Islam Hassan Sep 26 '17 at 20:45
  • I have specifed in my question that `I have to output the count of integers in the array which is divisible by k(one of the queries)`, so it will matter if I have duplicate divisors. Also, I have edited my question. – Pritom Mazumdar Sep 27 '17 at 04:06
  • You can use a hashmap instead of a hashset and keep the count in it while calculating the divisors. The main idea is to use hashing whether it's a hashset or a hashmap won't affect the complexity. – Islam Hassan Sep 27 '17 at 20:00
  • Buiding a table of all multiples is much simpler and faster. – maaartinus Sep 30 '17 at 16:48