0
$\begingroup$

I have an array ($|A|\leq 10^6$) of numbers ($A_i\leq10^6$) and a set of prime numbers. I have to find the count of the elements in the array that are divisible by at least one of the numbers in the given set.

For example:

Array: {3,5,7,15,21,143}

Set: {3,5,7}

Output : 5

The numbers are 3(3), 5(5), 7(7), 15(3,5), 21(3,7).

If the array size is $10^6$, an $n^2$ algorithm would time out.

Possible approach: I can preprocess all numbers in the array and store the count of elements each prime factors appear in.

For the example given above : The prime factors are 3,5,7,11,13 and values of the count array will be count[3]=3, count[5]=2, count[7]=2, count[11]=1, count[13]=1.

Can the principle of inclusion and exclusion be applied in this case or is there any other approach to the problem?

$\endgroup$
13
  • $\begingroup$ If you want to apply inclusion-exclusion, you also need count[3.5],count[3.7], count[5.7] and count[3.5.7] just to handle the {3,5,7} case. $\endgroup$ Oct 18, 2018 at 17:57
  • $\begingroup$ So does there exist an alternate solution? if so, please mention @HendrikJan $\endgroup$ Oct 18, 2018 at 18:03
  • 1
    $\begingroup$ Welcome to Computer Science! This looks like a nice problem. If it comes from an online programming contest or a coding camp, please add a URL. If it comes from a book or a paper, a reference. Besides paying proper attribution to the original source, all those information motivate and help people answer the question faster and better. Please add those information in the question since people and search engine are not expected to look at comments. $\endgroup$
    – John L.
    Oct 19, 2018 at 0:08
  • 1
    $\begingroup$ Indeed, I have not asked what is the typical distribution of the input fully yet! So, how many numbers in the array usually? Is it just about some tens, some hundreds, some thousands, some tens of thousands, some hundreds of thousand, or near a million? $\endgroup$
    – John L.
    Oct 19, 2018 at 7:53
  • 1
    $\begingroup$ This from an ongoing competition - Problem Link; in which OP is participating. I would avoid answering this question while the contest is ongoing to help preserve the integrity of the competition. $\endgroup$
    – xrisk
    Oct 19, 2018 at 9:13

5 Answers 5

1
$\begingroup$

One possible approach is to use the GCD algorithm: calculate the GCD of each number in your array with the product of the given primes.

$\endgroup$
1
$\begingroup$

If the number of numbers in the given array is no more than $10^6$, each of which is no larger than $10^6$, and the number of primes is no more than 10, then the way to move forward is apparently the following simplest algorithm in usual situations.

Initiate a boolean array A of False of size 1 plus the maximum of all numbers or just 1000001.
for each given prime number p:
    mark elements at A[p], A[2p], A[3p], etc until the end of array as True.
let count = 0
for each given number n:
    if A[n] is False, add count by 1
return count

The above algorithm is simple to code. It runs very fast since there is no division. It is likely to be faster than all other algorithms when the density of numbers is over 1/10, such as over $10^4$ numbers each of them is smaller than $10^5$, or over $10^5$ numbers each of them is smaller than $10^6$.

The algorithm could be improved if we also know or compute the smallest and the maximal number of all given numbers.

This algorithm will be very inefficient if we just have, for example, two numbers, 1 and $10^6$, and 10 primes numbers. However, it won't need a split of second on a normal computer, still. There is no visible incentive to go for a more efficient algorithm, which will probably be harder to code.

$\endgroup$
8
  • $\begingroup$ Can it be used to find those numbers which do not form a co prime pair with any of the rest of numbers? Like for eg : 2,3,6,10,12 So here 6 and 12 are the required numbers since they do not form a co prime pair at all. $\endgroup$ Oct 19, 2018 at 8:39
  • $\begingroup$ I spoke too soon. "find those numbers which do not form a co prime pair with any of the rest of numbers" is a lot harder. Thinking ... $\endgroup$
    – John L.
    Oct 19, 2018 at 9:02
  • $\begingroup$ That is why I asked for an optimized solution for the original problem. For each element if the complexity is logN then the overall complexity will just be NlogN which will pass $\endgroup$ Oct 19, 2018 at 9:06
  • 1
    $\begingroup$ This from an ongoing competition - Problem Link; in which OP is participating. I would avoid answering this question while the contest is ongoing to help preserve the integrity of the competition. $\endgroup$
    – xrisk
    Oct 19, 2018 at 9:14
  • 2
    $\begingroup$ That competition problem is not hard for me to do. However, since this is an ongoing competition, I will not provide more suggestion before the competition is over. Let me just say all the answers here are far from a valid answer for that competition problem. $\endgroup$
    – John L.
    Oct 19, 2018 at 9:24
0
$\begingroup$

Ok, so first and foremost: If some number X appears multiple times in A, we can calculate the answer for X once and just check the precalculated answer.

So basically, now we have 10^6 distinct numbers. AKA, 1,2,3...10^6. Good! So we just have to calculate the answer for all numbers between 1 and 10^6.

The second observation it's trivial to see that if the divisors set contains repeated numbers we can just erase the repetitions.

So now the divisors set only has distinct elements. Cool! Now a kinda brute force algorithm will work.

For each divisor X we will mark their multiples as "divisible". Please notice the number X has 10^6/X divisors.

You can see the code below of how this works:

#include <iostream>
#define MAX 1000005
///If I already added X to the set
bool already_computed[MAX];
///If the number X is divisible by someone in the set
bool seen[MAX];
int main(){
    ///First and foremost, we are reading the set
    int N;///Number of elements in the set
    std::cin>>N;
    for(int i=0;i!=N;++i){
        int x;
        std::cin>>x;
        ///If we didn't add x yet
        if(!already_computed[x]){
            ///Mark that you checked x
            already_computed[x]=true;
            ///Now I'm going to iterate EVERY single number upto 10^6
            ///I'm just checking the numbers that are divisible by X
            ///Please notice I'm checking 10^6/X numbers.
            int b=x;
            while(b<MAX){
                seen[b]=1;
                b+=x;
            }
        }
    }
    ///Now I'm reading the array
    int M;
    std::cin>>M;
    int answer=0;
    for(int i=0;i!=M;++i){
        int x;
        std::cin>>x;
        ///Notice that we already calculated our answer above :)
        answer+=seen[x];
     }
     std::cout<<answer<<"\n";
     return 0;
}

Here's the example the author gave us in the code's input format:

3
3 5 7
6
3 5 7 15 21 143

Ok, cool. At first glance this may seem like an optimized O(N^2), but it's actually O(N log N).

Proof: $\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+...\frac{1}{N}\approx log(N)$

Now multiplying the above equation by N:

$\frac{N}{1}+\frac{N}{2}+\frac{N}{3}+...\frac{N}{N}\approx N\cdot log(N)$

And the below fraction is EXACTLY the complexity of what we are doing in the loop where we insert the numbers contained in the set.

If you are interested in this equation please check the Harmonic Series https://en.wikipedia.org/wiki/Harmonic_series_(mathematics)

In my simulations the code above runs in around 30ms even in the worst-case scenarios, so I would say it's pretty efficient to solve the problem mentioned above.

$\endgroup$
0
$\begingroup$

Put all the primes in a sieve, ignoring duplicates. O(n), giving about n / ln n primes.

Put all the numbers in a sieve, counting multiplicity. O(n).

Take each prime in turn, count all multiples and how often they are present, then remove the multiples. The time is n / p, summed over the primes from 1 to n. I think that is O(n) as well.

$\endgroup$
-1
$\begingroup$

I think this process might give you the results Step1. know the no of elements Step2. Load the first prime number and check for divisibility. Step3. If the number in the array is divisible replace it with the prime you are dividing else Skip it. Step4. Load the next prime & repeat the process up to last prime in the set. Step5. Output={no of elements that are grater than largest prime number in the set}. I think the program goes like this

#include <stdio.h>#include < math.h> Int main() { Int x[100],y[20],z[100],I,j; Scanf/give x&y; For (i=1;i<=100;i++){ z[i]=x[i]; } For (j=1;j<=20,j++) { For(i=1;i<=100;i++) { z[i]=x[i]%y[j]; If(z[i]==0) { z[i]=y[j]; } else { z[i]=x[i]; } } } j=0; for (i=1;i<=100;i++) { If(z[i]>y[20]) { j++; } } Printf j; return 0; }

Ps:I skipped some syntax & I forgotten some syntax.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.