Count of co-prime pairs from two arrays in less than O(n^2) complexity

I came to this problem in a challenge.
There are two arrays A and B both of size of N and we need to return the count of pairs (A[i],B[j]) where gcd(A[i],B[j])==1 and A[i] != B[j].
I could only think of brute force approach which exceeded time limit for few test cases.

for(int i=0; i<n; i++) {

    for(int j=0; j<n; j++) {

        if(__gcd(a[i],b[j])==1) {

             printf("%d %dn", a[i], b[j]);

        }

    }

}

Can you advice time efficient algorithm to solve this.

Edit: Not able to share question link as this was from a hiring challenge. Adding the constraints and input/output format as I remember.

Input -

First line will contain N, the number of elements present in both arrays.

Second line will contain N space separated integers, elements of array A.

Third line will contain N space separated integers, elements of array B.

Output -

The count of pairs A[i],A[j] as per the conditions.

Constraints -

1 <= N <= 10^5

1 < A[i],B[j] <= 10^9 where i,j < N

edited Dec 28 '18 at 15:12

asked Dec 28 '18 at 10:33

Raja Dorji

5521315

5

Is there a bound on the size of the elements of A and B?

– Paul Hankin
Dec 28 '18 at 11:13

4

Why the i != j condition?

– Nelfeal
Dec 28 '18 at 11:18

1

Sorry,Initially I thought that this question can be done by Euler's totient function but I was unable to figure out any way to do that with it. Can you please share the question link so that I can help.

– Praveen Ojha
Dec 28 '18 at 12:52

1

@Nelfeal he meant sizes of the elements, not the array itself.

– meowgoesthedog
Dec 28 '18 at 12:53

1

Clearly, any O(n^2) algorithm is going to be too slow. You need to somehow make use of the fact that you don't need to produce the pairs, just count them, and design an O(n log n) or better algorithm.

– kfx
Dec 28 '18 at 15:02

|
show 5 more comments

for(int i=0; i<n; i++) {

    for(int j=0; j<n; j++) {

        if(__gcd(a[i],b[j])==1) {

             printf("%d %dn", a[i], b[j]);

        }

    }

}

Can you advice time efficient algorithm to solve this.

Edit: Not able to share question link as this was from a hiring challenge. Adding the constraints and input/output format as I remember.

Input -

First line will contain N, the number of elements present in both arrays.

Second line will contain N space separated integers, elements of array A.

Third line will contain N space separated integers, elements of array B.

Output -

The count of pairs A[i],A[j] as per the conditions.

Constraints -

1 <= N <= 10^5

1 < A[i],B[j] <= 10^9 where i,j < N

edited Dec 28 '18 at 15:12

asked Dec 28 '18 at 10:33

Raja Dorji

5521315

5

Is there a bound on the size of the elements of A and B?

– Paul Hankin
Dec 28 '18 at 11:13

4

Why the i != j condition?

– Nelfeal
Dec 28 '18 at 11:18

1

Sorry,Initially I thought that this question can be done by Euler's totient function but I was unable to figure out any way to do that with it. Can you please share the question link so that I can help.

– Praveen Ojha
Dec 28 '18 at 12:52

1

@Nelfeal he meant sizes of the elements, not the array itself.

– meowgoesthedog
Dec 28 '18 at 12:53

1

Clearly, any O(n^2) algorithm is going to be too slow. You need to somehow make use of the fact that you don't need to produce the pairs, just count them, and design an O(n log n) or better algorithm.

– kfx
Dec 28 '18 at 15:02

|
show 5 more comments

for(int i=0; i<n; i++) {

    for(int j=0; j<n; j++) {

        if(__gcd(a[i],b[j])==1) {

             printf("%d %dn", a[i], b[j]);

        }

    }

}

Can you advice time efficient algorithm to solve this.

Edit: Not able to share question link as this was from a hiring challenge. Adding the constraints and input/output format as I remember.

Input -

First line will contain N, the number of elements present in both arrays.

Second line will contain N space separated integers, elements of array A.

Third line will contain N space separated integers, elements of array B.

Output -

The count of pairs A[i],A[j] as per the conditions.

Constraints -

1 <= N <= 10^5

1 < A[i],B[j] <= 10^9 where i,j < N

edited Dec 28 '18 at 15:12

asked Dec 28 '18 at 10:33

Raja Dorji

5521315

for(int i=0; i<n; i++) {

    for(int j=0; j<n; j++) {

        if(__gcd(a[i],b[j])==1) {

             printf("%d %dn", a[i], b[j]);

        }

    }

}

Can you advice time efficient algorithm to solve this.

Edit: Not able to share question link as this was from a hiring challenge. Adding the constraints and input/output format as I remember.

Input -

First line will contain N, the number of elements present in both arrays.

Second line will contain N space separated integers, elements of array A.

Third line will contain N space separated integers, elements of array B.

Output -

The count of pairs A[i],A[j] as per the conditions.

Constraints -

1 <= N <= 10^5

1 < A[i],B[j] <= 10^9 where i,j < N

algorithm time-complexity

edited Dec 28 '18 at 15:12

asked Dec 28 '18 at 10:33

Raja Dorji

5521315

edited Dec 28 '18 at 15:12

asked Dec 28 '18 at 10:33

Raja Dorji

5521315

edited Dec 28 '18 at 15:12

asked Dec 28 '18 at 10:33

Raja Dorji

5521315

asked Dec 28 '18 at 10:33

Raja Dorji

5521315

asked Dec 28 '18 at 10:33

Raja Dorji

5521315

5

Is there a bound on the size of the elements of A and B?

– Paul Hankin
Dec 28 '18 at 11:13

4

Why the i != j condition?

– Nelfeal
Dec 28 '18 at 11:18

1

Sorry,Initially I thought that this question can be done by Euler's totient function but I was unable to figure out any way to do that with it. Can you please share the question link so that I can help.

– Praveen Ojha
Dec 28 '18 at 12:52

1

@Nelfeal he meant sizes of the elements, not the array itself.

– meowgoesthedog
Dec 28 '18 at 12:53

1

Clearly, any O(n^2) algorithm is going to be too slow. You need to somehow make use of the fact that you don't need to produce the pairs, just count them, and design an O(n log n) or better algorithm.

– kfx
Dec 28 '18 at 15:02

|
show 5 more comments

5

Is there a bound on the size of the elements of A and B?

– Paul Hankin
Dec 28 '18 at 11:13

4

Why the i != j condition?

– Nelfeal
Dec 28 '18 at 11:18

1

Sorry,Initially I thought that this question can be done by Euler's totient function but I was unable to figure out any way to do that with it. Can you please share the question link so that I can help.

– Praveen Ojha
Dec 28 '18 at 12:52

1

@Nelfeal he meant sizes of the elements, not the array itself.

– meowgoesthedog
Dec 28 '18 at 12:53

1

Clearly, any O(n^2) algorithm is going to be too slow. You need to somehow make use of the fact that you don't need to produce the pairs, just count them, and design an O(n log n) or better algorithm.

– kfx
Dec 28 '18 at 15:02

Is there a bound on the size of the elements of A and B?

– Paul Hankin
Dec 28 '18 at 11:13

Why the i != j condition?

– Nelfeal
Dec 28 '18 at 11:18

Sorry,Initially I thought that this question can be done by Euler's totient function but I was unable to figure out any way to do that with it. Can you please share the question link so that I can help.

– Praveen Ojha
Dec 28 '18 at 12:52

@Nelfeal he meant sizes of the elements, not the array itself.

– meowgoesthedog
Dec 28 '18 at 12:53

Clearly, any O(n^2) algorithm is going to be too slow. You need to somehow make use of the fact that you don't need to produce the pairs, just count them, and design an O(n log n) or better algorithm.

– kfx
Dec 28 '18 at 15:02

|
show 5 more comments

1 Answer
1

active

oldest

votes

The first step is to use Eratosthenes sieve to calculate the prime numbers up to sqrt(10^9). This sieve can then be used to quickly find all prime factors of any number less than 10^9 (see the getPrimeFactors(...) function in the code sample below).

Next, for each A[i] with prime factors p0, p1, ..., pk, we compute all possible sub-products X - p0, p1, p0p1, p2, p0p2, p1p2, p0p1p2, p3, p0p3, ..., p0p1p2...pk and count them in map cntp[X]. Effectively, the map cntp[X] tells us the number of elements A[i] divisible by X, where X is a product of prime numbers to the power of 0 or 1. So for example, for the number A[i] = 12, the prime factors are 2, 3. We will count cntp[2]++, cntp[3]++ and cntp[6]++.

Finally, for each B[j] with prime factors p0, p1, ..., pk, we again compute all possible sub-products X and use the Inclusion-exclusion principle to count all non-coprime pairs C_j (i.e. the number of A[i]s that share at least one prime factor with B[j]). The numbers C_j are then subtracted from the total number of pairs - N*N to get the final answer.

Note: the Inclusion-exclusion principle looks like this:

C_j = (cntp[p0] + cntp[p1] + ... + cntp[pk]) -

      (cntp[p0p1] + cntp[p0p2] + ... + cntp[pk-1pk]) +

      (cntp[p0p1p2] + cntp[p0p1p3] + ... + cntp[pk-2pk-1pk]) -

      ...

and accounts for the fact that in cntp[X] and cntp[Y] we could have counted the same number A[i] twice, given that it is divisible by both X and Y.

Here is a possible C++ implementation of the algorithm, which produces the same results as the naive O(n^2) algorithm by OP:

// get prime factors of a using pre-generated sieve

std::vector<int> getPrimeFactors(int a, const std::vector<int> & primes) {

    std::vector<int> f;

    for (auto p : primes) {

        if (p > a) break;

        if (a % p == 0) {

            f.push_back(p);

            do {

                a /= p;

            } while (a % p == 0);

        }

    }

    if (a > 1) f.push_back(a);



    return f;

}



// find coprime pairs A_i and B_j

// A_i and B_i <= 1e9

void solution(const std::vector<int> & A, const std::vector<int> & B) {

    // generate prime sieve

    std::vector<int> primes;

    primes.push_back(2);



    for (int i = 3; i*i <= 1e9; ++i) {

        bool isPrime = true;

        for (auto p : primes) {

            if (i % p == 0) {

                isPrime = false;

                break;

            }

        }

        if (isPrime) {

            primes.push_back(i);

        }

    }



    int N = A.size();



    struct Entry {

        int n = 0;

        int64_t p = 0;

    };



    // cntp[X] - number of times the product X can be expressed

    // with prime factors of A_i

    std::map<int64_t, int64_t> cntp;



    for (int i = 0; i < N; i++) {

        auto f = getPrimeFactors(A[i], primes);



        // count possible products using non-repeating prime factors of A_i

        std::vector<Entry> x;

        x.push_back({ 0, 1 });



        for (auto p : f) {

            int k = x.size();

            for (int i = 0; i < k; ++i) {

                int nn = x[i].n + 1;

                int64_t pp = x[i].p*p;



                ++cntp[pp];

                x.push_back({ nn, pp });

            }

        }

    }



    // use Inclusion–exclusion principle to count non-coprime pairs

    // and subtract them from the total number of prairs N*N



    int64_t cnt = N; cnt *= N;



    for (int i = 0; i < N; i++) {

        auto f = getPrimeFactors(B[i], primes);



        std::vector<Entry> x;

        x.push_back({ 0, 1 });



        for (auto p : f) {

            int k = x.size();

            for (int i = 0; i < k; ++i) {

                int nn = x[i].n + 1;

                int64_t pp = x[i].p*p;



                x.push_back({ nn, pp });



                if (nn % 2 == 1) {

                    cnt -= cntp[pp];

                } else {

                    cnt += cntp[pp];

                }

            }

        }

    }



    printf("cnt = %dn", (int) cnt);

}

Live example

I cannot estimate the complexity analytically, but here are some profiling result on my laptop for different N and uniformly random A[i] and B[j]:

For N = 1e2, takes ~0.02 sec

For N = 1e3, takes ~0.05 sec

For N = 1e4, takes ~0.38 sec

For N = 1e5, takes ~3.80 sec

For comparison, the O(n^2) approach takes:

For N = 1e2, takes ~0.00 sec

For N = 1e3, takes ~0.15 sec

For N = 1e4, takes ~15.1 sec

For N = 1e5, takes too long, didn't wait to finish

edited Jan 1 at 12:34

answered Dec 28 '18 at 18:40

Georgi Gerganov

776611

1

With s^2 the upper bound on the elements of A and B, building the sieve is O(s log log s). Factoring each element is at most O(log log s), so for all elements, it's O(n log log s). If you only take into account distinct prime factors (because you can), there are less than 2^(log log s) = (log s)^(log 2) < s sub-products for any element, so for all elements, computing the sub-products (and counting all non-coprime pairs) is at most O(s). Summing all that up gives an (over)estimate O((s+n) log log s), and if s ~ n, O(n log log n).

– Nelfeal
Dec 29 '18 at 6:49

That said, the problem states an upper bound on n, which is stupid since it makes any solution automatically O(1).

– Nelfeal
Dec 29 '18 at 6:51

Thanks for the complexity analysis. What do you mean by "it makes any solutions automatically O(1)"? You still need to iterate over the elements, so it cannot be less than O(n) in any case.

– Georgi Gerganov
Dec 29 '18 at 22:32

Let M be the upper bound on n (M = 10^5 in the question). Any solution will have a runtime as an increasing function of n; let f be that function for any particular solution, so its runtime is f(n). The problem that the upper bound introduces is that this particular solution will never have a runtime greater than f(M), which means you can simply say that its complexity is O(f(M)). And because f(M) is constant, that's equivalent to O(1). It might be a very large constant, but it defeats the purpose of complexity analysis (where n is supposed to grow indefinitely).

– Nelfeal
Dec 30 '18 at 5:49

add a comment |

Your Answer

StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});

}
});

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53957088%2fcount-of-co-prime-pairs-from-two-arrays-in-less-than-on2-complexity%23new-answer', 'question_page');
}
);

Post as a guest

Name

Required, but never shown

1 Answer
1

active

oldest

votes

1 Answer
1

active

oldest

votes

Note: the Inclusion-exclusion principle looks like this:

C_j = (cntp[p0] + cntp[p1] + ... + cntp[pk]) -

      (cntp[p0p1] + cntp[p0p2] + ... + cntp[pk-1pk]) +

      (cntp[p0p1p2] + cntp[p0p1p3] + ... + cntp[pk-2pk-1pk]) -

      ...

and accounts for the fact that in cntp[X] and cntp[Y] we could have counted the same number A[i] twice, given that it is divisible by both X and Y.

Here is a possible C++ implementation of the algorithm, which produces the same results as the naive O(n^2) algorithm by OP:

// get prime factors of a using pre-generated sieve

std::vector<int> getPrimeFactors(int a, const std::vector<int> & primes) {

    std::vector<int> f;

    for (auto p : primes) {

        if (p > a) break;

        if (a % p == 0) {

            f.push_back(p);

            do {

                a /= p;

            } while (a % p == 0);

        }

    }

    if (a > 1) f.push_back(a);



    return f;

}



// find coprime pairs A_i and B_j

// A_i and B_i <= 1e9

void solution(const std::vector<int> & A, const std::vector<int> & B) {

    // generate prime sieve

    std::vector<int> primes;

    primes.push_back(2);



    for (int i = 3; i*i <= 1e9; ++i) {

        bool isPrime = true;

        for (auto p : primes) {

            if (i % p == 0) {

                isPrime = false;

                break;

            }

        }

        if (isPrime) {

            primes.push_back(i);

        }

    }



    int N = A.size();



    struct Entry {

        int n = 0;

        int64_t p = 0;

    };



    // cntp[X] - number of times the product X can be expressed

    // with prime factors of A_i

    std::map<int64_t, int64_t> cntp;



    for (int i = 0; i < N; i++) {

        auto f = getPrimeFactors(A[i], primes);



        // count possible products using non-repeating prime factors of A_i

        std::vector<Entry> x;

        x.push_back({ 0, 1 });



        for (auto p : f) {

            int k = x.size();

            for (int i = 0; i < k; ++i) {

                int nn = x[i].n + 1;

                int64_t pp = x[i].p*p;



                ++cntp[pp];

                x.push_back({ nn, pp });

            }

        }

    }



    // use Inclusion–exclusion principle to count non-coprime pairs

    // and subtract them from the total number of prairs N*N



    int64_t cnt = N; cnt *= N;



    for (int i = 0; i < N; i++) {

        auto f = getPrimeFactors(B[i], primes);



        std::vector<Entry> x;

        x.push_back({ 0, 1 });



        for (auto p : f) {

            int k = x.size();

            for (int i = 0; i < k; ++i) {

                int nn = x[i].n + 1;

                int64_t pp = x[i].p*p;



                x.push_back({ nn, pp });



                if (nn % 2 == 1) {

                    cnt -= cntp[pp];

                } else {

                    cnt += cntp[pp];

                }

            }

        }

    }



    printf("cnt = %dn", (int) cnt);

}

Live example

I cannot estimate the complexity analytically, but here are some profiling result on my laptop for different N and uniformly random A[i] and B[j]:

For N = 1e2, takes ~0.02 sec

For N = 1e3, takes ~0.05 sec

For N = 1e4, takes ~0.38 sec

For N = 1e5, takes ~3.80 sec

For comparison, the O(n^2) approach takes:

For N = 1e2, takes ~0.00 sec

For N = 1e3, takes ~0.15 sec

For N = 1e4, takes ~15.1 sec

For N = 1e5, takes too long, didn't wait to finish

edited Jan 1 at 12:34

answered Dec 28 '18 at 18:40

Georgi Gerganov

776611

1

With s^2 the upper bound on the elements of A and B, building the sieve is O(s log log s). Factoring each element is at most O(log log s), so for all elements, it's O(n log log s). If you only take into account distinct prime factors (because you can), there are less than 2^(log log s) = (log s)^(log 2) < s sub-products for any element, so for all elements, computing the sub-products (and counting all non-coprime pairs) is at most O(s). Summing all that up gives an (over)estimate O((s+n) log log s), and if s ~ n, O(n log log n).

– Nelfeal
Dec 29 '18 at 6:49

That said, the problem states an upper bound on n, which is stupid since it makes any solution automatically O(1).

– Nelfeal
Dec 29 '18 at 6:51

Thanks for the complexity analysis. What do you mean by "it makes any solutions automatically O(1)"? You still need to iterate over the elements, so it cannot be less than O(n) in any case.

– Georgi Gerganov
Dec 29 '18 at 22:32

Let M be the upper bound on n (M = 10^5 in the question). Any solution will have a runtime as an increasing function of n; let f be that function for any particular solution, so its runtime is f(n). The problem that the upper bound introduces is that this particular solution will never have a runtime greater than f(M), which means you can simply say that its complexity is O(f(M)). And because f(M) is constant, that's equivalent to O(1). It might be a very large constant, but it defeats the purpose of complexity analysis (where n is supposed to grow indefinitely).

– Nelfeal
Dec 30 '18 at 5:49

add a comment |

Note: the Inclusion-exclusion principle looks like this:

C_j = (cntp[p0] + cntp[p1] + ... + cntp[pk]) -

      (cntp[p0p1] + cntp[p0p2] + ... + cntp[pk-1pk]) +

      (cntp[p0p1p2] + cntp[p0p1p3] + ... + cntp[pk-2pk-1pk]) -

      ...

and accounts for the fact that in cntp[X] and cntp[Y] we could have counted the same number A[i] twice, given that it is divisible by both X and Y.

Here is a possible C++ implementation of the algorithm, which produces the same results as the naive O(n^2) algorithm by OP:

// get prime factors of a using pre-generated sieve

std::vector<int> getPrimeFactors(int a, const std::vector<int> & primes) {

    std::vector<int> f;

    for (auto p : primes) {

        if (p > a) break;

        if (a % p == 0) {

            f.push_back(p);

            do {

                a /= p;

            } while (a % p == 0);

        }

    }

    if (a > 1) f.push_back(a);



    return f;

}



// find coprime pairs A_i and B_j

// A_i and B_i <= 1e9

void solution(const std::vector<int> & A, const std::vector<int> & B) {

    // generate prime sieve

    std::vector<int> primes;

    primes.push_back(2);



    for (int i = 3; i*i <= 1e9; ++i) {

        bool isPrime = true;

        for (auto p : primes) {

            if (i % p == 0) {

                isPrime = false;

                break;

            }

        }

        if (isPrime) {

            primes.push_back(i);

        }

    }



    int N = A.size();



    struct Entry {

        int n = 0;

        int64_t p = 0;

    };



    // cntp[X] - number of times the product X can be expressed

    // with prime factors of A_i

    std::map<int64_t, int64_t> cntp;



    for (int i = 0; i < N; i++) {

        auto f = getPrimeFactors(A[i], primes);



        // count possible products using non-repeating prime factors of A_i

        std::vector<Entry> x;

        x.push_back({ 0, 1 });



        for (auto p : f) {

            int k = x.size();

            for (int i = 0; i < k; ++i) {

                int nn = x[i].n + 1;

                int64_t pp = x[i].p*p;



                ++cntp[pp];

                x.push_back({ nn, pp });

            }

        }

    }



    // use Inclusion–exclusion principle to count non-coprime pairs

    // and subtract them from the total number of prairs N*N



    int64_t cnt = N; cnt *= N;



    for (int i = 0; i < N; i++) {

        auto f = getPrimeFactors(B[i], primes);



        std::vector<Entry> x;

        x.push_back({ 0, 1 });



        for (auto p : f) {

            int k = x.size();

            for (int i = 0; i < k; ++i) {

                int nn = x[i].n + 1;

                int64_t pp = x[i].p*p;



                x.push_back({ nn, pp });



                if (nn % 2 == 1) {

                    cnt -= cntp[pp];

                } else {

                    cnt += cntp[pp];

                }

            }

        }

    }



    printf("cnt = %dn", (int) cnt);

}

Live example

I cannot estimate the complexity analytically, but here are some profiling result on my laptop for different N and uniformly random A[i] and B[j]:

For N = 1e2, takes ~0.02 sec

For N = 1e3, takes ~0.05 sec

For N = 1e4, takes ~0.38 sec

For N = 1e5, takes ~3.80 sec

For comparison, the O(n^2) approach takes:

For N = 1e2, takes ~0.00 sec

For N = 1e3, takes ~0.15 sec

For N = 1e4, takes ~15.1 sec

For N = 1e5, takes too long, didn't wait to finish

edited Jan 1 at 12:34

answered Dec 28 '18 at 18:40

Georgi Gerganov

776611

1

With s^2 the upper bound on the elements of A and B, building the sieve is O(s log log s). Factoring each element is at most O(log log s), so for all elements, it's O(n log log s). If you only take into account distinct prime factors (because you can), there are less than 2^(log log s) = (log s)^(log 2) < s sub-products for any element, so for all elements, computing the sub-products (and counting all non-coprime pairs) is at most O(s). Summing all that up gives an (over)estimate O((s+n) log log s), and if s ~ n, O(n log log n).

– Nelfeal
Dec 29 '18 at 6:49

That said, the problem states an upper bound on n, which is stupid since it makes any solution automatically O(1).

– Nelfeal
Dec 29 '18 at 6:51

Thanks for the complexity analysis. What do you mean by "it makes any solutions automatically O(1)"? You still need to iterate over the elements, so it cannot be less than O(n) in any case.

– Georgi Gerganov
Dec 29 '18 at 22:32

Let M be the upper bound on n (M = 10^5 in the question). Any solution will have a runtime as an increasing function of n; let f be that function for any particular solution, so its runtime is f(n). The problem that the upper bound introduces is that this particular solution will never have a runtime greater than f(M), which means you can simply say that its complexity is O(f(M)). And because f(M) is constant, that's equivalent to O(1). It might be a very large constant, but it defeats the purpose of complexity analysis (where n is supposed to grow indefinitely).

– Nelfeal
Dec 30 '18 at 5:49

add a comment |

Note: the Inclusion-exclusion principle looks like this:

C_j = (cntp[p0] + cntp[p1] + ... + cntp[pk]) -

      (cntp[p0p1] + cntp[p0p2] + ... + cntp[pk-1pk]) +

      (cntp[p0p1p2] + cntp[p0p1p3] + ... + cntp[pk-2pk-1pk]) -

      ...

and accounts for the fact that in cntp[X] and cntp[Y] we could have counted the same number A[i] twice, given that it is divisible by both X and Y.

Here is a possible C++ implementation of the algorithm, which produces the same results as the naive O(n^2) algorithm by OP:

// get prime factors of a using pre-generated sieve

std::vector<int> getPrimeFactors(int a, const std::vector<int> & primes) {

    std::vector<int> f;

    for (auto p : primes) {

        if (p > a) break;

        if (a % p == 0) {

            f.push_back(p);

            do {

                a /= p;

            } while (a % p == 0);

        }

    }

    if (a > 1) f.push_back(a);



    return f;

}



// find coprime pairs A_i and B_j

// A_i and B_i <= 1e9

void solution(const std::vector<int> & A, const std::vector<int> & B) {

    // generate prime sieve

    std::vector<int> primes;

    primes.push_back(2);



    for (int i = 3; i*i <= 1e9; ++i) {

        bool isPrime = true;

        for (auto p : primes) {

            if (i % p == 0) {

                isPrime = false;

                break;

            }

        }

        if (isPrime) {

            primes.push_back(i);

        }

    }



    int N = A.size();



    struct Entry {

        int n = 0;

        int64_t p = 0;

    };



    // cntp[X] - number of times the product X can be expressed

    // with prime factors of A_i

    std::map<int64_t, int64_t> cntp;



    for (int i = 0; i < N; i++) {

        auto f = getPrimeFactors(A[i], primes);



        // count possible products using non-repeating prime factors of A_i

        std::vector<Entry> x;

        x.push_back({ 0, 1 });



        for (auto p : f) {

            int k = x.size();

            for (int i = 0; i < k; ++i) {

                int nn = x[i].n + 1;

                int64_t pp = x[i].p*p;



                ++cntp[pp];

                x.push_back({ nn, pp });

            }

        }

    }



    // use Inclusion–exclusion principle to count non-coprime pairs

    // and subtract them from the total number of prairs N*N



    int64_t cnt = N; cnt *= N;



    for (int i = 0; i < N; i++) {

        auto f = getPrimeFactors(B[i], primes);



        std::vector<Entry> x;

        x.push_back({ 0, 1 });



        for (auto p : f) {

            int k = x.size();

            for (int i = 0; i < k; ++i) {

                int nn = x[i].n + 1;

                int64_t pp = x[i].p*p;



                x.push_back({ nn, pp });



                if (nn % 2 == 1) {

                    cnt -= cntp[pp];

                } else {

                    cnt += cntp[pp];

                }

            }

        }

    }



    printf("cnt = %dn", (int) cnt);

}

Live example

I cannot estimate the complexity analytically, but here are some profiling result on my laptop for different N and uniformly random A[i] and B[j]:

For N = 1e2, takes ~0.02 sec

For N = 1e3, takes ~0.05 sec

For N = 1e4, takes ~0.38 sec

For N = 1e5, takes ~3.80 sec

For comparison, the O(n^2) approach takes:

For N = 1e2, takes ~0.00 sec

For N = 1e3, takes ~0.15 sec

For N = 1e4, takes ~15.1 sec

For N = 1e5, takes too long, didn't wait to finish

edited Jan 1 at 12:34

answered Dec 28 '18 at 18:40

Georgi Gerganov

776611

Note: the Inclusion-exclusion principle looks like this:

C_j = (cntp[p0] + cntp[p1] + ... + cntp[pk]) -

      (cntp[p0p1] + cntp[p0p2] + ... + cntp[pk-1pk]) +

      (cntp[p0p1p2] + cntp[p0p1p3] + ... + cntp[pk-2pk-1pk]) -

      ...

and accounts for the fact that in cntp[X] and cntp[Y] we could have counted the same number A[i] twice, given that it is divisible by both X and Y.

Here is a possible C++ implementation of the algorithm, which produces the same results as the naive O(n^2) algorithm by OP:

// get prime factors of a using pre-generated sieve

std::vector<int> getPrimeFactors(int a, const std::vector<int> & primes) {

    std::vector<int> f;

    for (auto p : primes) {

        if (p > a) break;

        if (a % p == 0) {

            f.push_back(p);

            do {

                a /= p;

            } while (a % p == 0);

        }

    }

    if (a > 1) f.push_back(a);



    return f;

}



// find coprime pairs A_i and B_j

// A_i and B_i <= 1e9

void solution(const std::vector<int> & A, const std::vector<int> & B) {

    // generate prime sieve

    std::vector<int> primes;

    primes.push_back(2);



    for (int i = 3; i*i <= 1e9; ++i) {

        bool isPrime = true;

        for (auto p : primes) {

            if (i % p == 0) {

                isPrime = false;

                break;

            }

        }

        if (isPrime) {

            primes.push_back(i);

        }

    }



    int N = A.size();



    struct Entry {

        int n = 0;

        int64_t p = 0;

    };



    // cntp[X] - number of times the product X can be expressed

    // with prime factors of A_i

    std::map<int64_t, int64_t> cntp;



    for (int i = 0; i < N; i++) {

        auto f = getPrimeFactors(A[i], primes);



        // count possible products using non-repeating prime factors of A_i

        std::vector<Entry> x;

        x.push_back({ 0, 1 });



        for (auto p : f) {

            int k = x.size();

            for (int i = 0; i < k; ++i) {

                int nn = x[i].n + 1;

                int64_t pp = x[i].p*p;



                ++cntp[pp];

                x.push_back({ nn, pp });

            }

        }

    }



    // use Inclusion–exclusion principle to count non-coprime pairs

    // and subtract them from the total number of prairs N*N



    int64_t cnt = N; cnt *= N;



    for (int i = 0; i < N; i++) {

        auto f = getPrimeFactors(B[i], primes);



        std::vector<Entry> x;

        x.push_back({ 0, 1 });



        for (auto p : f) {

            int k = x.size();

            for (int i = 0; i < k; ++i) {

                int nn = x[i].n + 1;

                int64_t pp = x[i].p*p;



                x.push_back({ nn, pp });



                if (nn % 2 == 1) {

                    cnt -= cntp[pp];

                } else {

                    cnt += cntp[pp];

                }

            }

        }

    }



    printf("cnt = %dn", (int) cnt);

}

Live example

I cannot estimate the complexity analytically, but here are some profiling result on my laptop for different N and uniformly random A[i] and B[j]:

For N = 1e2, takes ~0.02 sec

For N = 1e3, takes ~0.05 sec

For N = 1e4, takes ~0.38 sec

For N = 1e5, takes ~3.80 sec

For comparison, the O(n^2) approach takes:

For N = 1e2, takes ~0.00 sec

For N = 1e3, takes ~0.15 sec

For N = 1e4, takes ~15.1 sec

For N = 1e5, takes too long, didn't wait to finish

edited Jan 1 at 12:34

answered Dec 28 '18 at 18:40

Georgi Gerganov

776611

edited Jan 1 at 12:34

answered Dec 28 '18 at 18:40

Georgi Gerganov

776611

answered Dec 28 '18 at 18:40

Georgi Gerganov

776611

answered Dec 28 '18 at 18:40

Georgi Gerganov

776611

1

With s^2 the upper bound on the elements of A and B, building the sieve is O(s log log s). Factoring each element is at most O(log log s), so for all elements, it's O(n log log s). If you only take into account distinct prime factors (because you can), there are less than 2^(log log s) = (log s)^(log 2) < s sub-products for any element, so for all elements, computing the sub-products (and counting all non-coprime pairs) is at most O(s). Summing all that up gives an (over)estimate O((s+n) log log s), and if s ~ n, O(n log log n).

– Nelfeal
Dec 29 '18 at 6:49

That said, the problem states an upper bound on n, which is stupid since it makes any solution automatically O(1).

– Nelfeal
Dec 29 '18 at 6:51

Thanks for the complexity analysis. What do you mean by "it makes any solutions automatically O(1)"? You still need to iterate over the elements, so it cannot be less than O(n) in any case.

– Georgi Gerganov
Dec 29 '18 at 22:32

Let M be the upper bound on n (M = 10^5 in the question). Any solution will have a runtime as an increasing function of n; let f be that function for any particular solution, so its runtime is f(n). The problem that the upper bound introduces is that this particular solution will never have a runtime greater than f(M), which means you can simply say that its complexity is O(f(M)). And because f(M) is constant, that's equivalent to O(1). It might be a very large constant, but it defeats the purpose of complexity analysis (where n is supposed to grow indefinitely).

– Nelfeal
Dec 30 '18 at 5:49

add a comment |

1

With s^2 the upper bound on the elements of A and B, building the sieve is O(s log log s). Factoring each element is at most O(log log s), so for all elements, it's O(n log log s). If you only take into account distinct prime factors (because you can), there are less than 2^(log log s) = (log s)^(log 2) < s sub-products for any element, so for all elements, computing the sub-products (and counting all non-coprime pairs) is at most O(s). Summing all that up gives an (over)estimate O((s+n) log log s), and if s ~ n, O(n log log n).

– Nelfeal
Dec 29 '18 at 6:49

That said, the problem states an upper bound on n, which is stupid since it makes any solution automatically O(1).

– Nelfeal
Dec 29 '18 at 6:51

Thanks for the complexity analysis. What do you mean by "it makes any solutions automatically O(1)"? You still need to iterate over the elements, so it cannot be less than O(n) in any case.

– Georgi Gerganov
Dec 29 '18 at 22:32

Let M be the upper bound on n (M = 10^5 in the question). Any solution will have a runtime as an increasing function of n; let f be that function for any particular solution, so its runtime is f(n). The problem that the upper bound introduces is that this particular solution will never have a runtime greater than f(M), which means you can simply say that its complexity is O(f(M)). And because f(M) is constant, that's equivalent to O(1). It might be a very large constant, but it defeats the purpose of complexity analysis (where n is supposed to grow indefinitely).

– Nelfeal
Dec 30 '18 at 5:49

With s^2 the upper bound on the elements of A and B, building the sieve is O(s log log s). Factoring each element is at most O(log log s), so for all elements, it's O(n log log s). If you only take into account distinct prime factors (because you can), there are less than 2^(log log s) = (log s)^(log 2) < s sub-products for any element, so for all elements, computing the sub-products (and counting all non-coprime pairs) is at most O(s). Summing all that up gives an (over)estimate O((s+n) log log s), and if s ~ n, O(n log log n).

– Nelfeal
Dec 29 '18 at 6:49

That said, the problem states an upper bound on n, which is stupid since it makes any solution automatically O(1).

– Nelfeal
Dec 29 '18 at 6:51

Thanks for the complexity analysis. What do you mean by "it makes any solutions automatically O(1)"? You still need to iterate over the elements, so it cannot be less than O(n) in any case.

– Georgi Gerganov
Dec 29 '18 at 22:32

Let M be the upper bound on n (M = 10^5 in the question). Any solution will have a runtime as an increasing function of n; let f be that function for any particular solution, so its runtime is f(n). The problem that the upper bound introduces is that this particular solution will never have a runtime greater than f(M), which means you can simply say that its complexity is O(f(M)). And because f(M) is constant, that's equivalent to O(1). It might be a very large constant, but it defeats the purpose of complexity analysis (where n is supposed to grow indefinitely).

– Nelfeal
Dec 30 '18 at 5:49

add a comment |

draft saved

draft discarded

Thanks for contributing an answer to Stack Overflow!

Please be sure to answer the question. Provide details and share your research!

But avoid …

Asking for help, clarification, or responding to other answers.

Making statements based on opinion; back them up with references or personal experience.

To learn more, see our tips on writing great answers.

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Name

Required, but never shown

Name

Required, but never shown

This page is only for reference, If you need detailed information, please check here

Search This Blog

Ufyukyu