Co-prime Twins

Hard
0/120
Average time to solve is 70m
profile
Contributed by
13 upvotes
Asked in companies
Tekion CorpNetlink

Problem statement

A pair of positive integers (a, b) is said to be a coprime-twin pair, if for all positive integers x, both a and b and are coprime to x or both and are not coprime to x. Formally, 2 distinct positive integers a and b can form a coprime-twin pair if and only if S(a) = S(b), where S(x) denotes the set of all positive integers that are coprime to x.

For example: 
2 and 4 are coprime-twin pairs.
1 and 2 are not coprime-twin pairs.


The score of a sequence a1, a2, .. an is the number of indices (i, j) such that i < j and the pair (ai, aj) forms a coprime-twin pair.

You are given an array A of positive integers and Q queries of the form L, R. For each query, determine the score of the subarray [L,  R] inclusive.

Note: A subarray is a contiguous non-empty segment of the array.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains a single integer ‘T’ denoting the number of test cases to be run. Then the test cases follow.

The first line of each test case contains two space-separated integers N and Q which denote the number of elements in the array A and the number of queries you need to answer respectively.

The next line contains N space-separated integers denoting the array a1, a2, … an.
The next Q lines contain two integers each - Li and Ri, the parameters of the ith query.
Output Format: 
For each test case, Q lines

For each of the next Q lines, print a single integer denoting the answer for the ith query.
Note: 
You are not required to print anything; it has already been taken care of. Just implement the function.
Constraints: 
1 <= T <= 10
1 <= N, Q <= 10^4
1 <= Ai <= 10^6
1 <= L <= R <= N

Time Limit: 1 sec.
Sample Input 1:
1
6 4
2 4 6 8 6 4
3 5
2 4
1 4
1 5
Sample Output 1:
1
1
3
4
Explanation For Sample Output 1:
For the first query, (6,6) is the coprime twin pair.
For the second query, (4, 8) is the twin pair.
For the third query, (2, 4), (2, 8) and (4, 8) are the co primes twins.
For the 4th query, (2, 4), (2, 8),(6, 6) and (4, 8) are the required pairs.
Sample Input 2:
2
1 1
7
1 1
2 1
3 9
1 2
Sample Output 2:
0 
1
Hint

Think of relating the set of primes of two numbers if they are coprime twins.

Approaches (2)
Brute Force simulation

Two numbers are called co-prime twins if and only if the set of primes in its prime factorization is equal.

 

So for any number, we need to reduce any power of a prime to only single if we want to compare the sets.

If x = p1^x1*p2^x2 … pk^xk

 

we can reduce it to 

x = p1 * p2 * p, .. pk

 

Now, this can be done using pre-computation of primes using a sieve of Eratosthenes.

 Now we just need to count for each query the number of equal pairs in that range which can be done using a count array.. 


 Algorithm:

 

coprimeTwins (Q, A) returns the answer for each of the queries in Q.

  1. Call pre-computation function to calculate the reduced form of each number from 1 to MAX.
  2. Replace each of the array elements to its reduced form.
  3. Now for each query L, R iterate from L to R and increase the answer by cnt[arr[i]] and increase it by 1.
  4. Finally, reset the cnt array to zero again.


 

precompute(reduced) returns an array where each index stores its reduced form.

  1. We run a sieve from 1 to MAX and if reduced[i] == 1 (it is a prime) then we iterate over all its multiples and multiply reduced[j] by i.
Time Complexity

O(MAX*log(MAX) + Q*N) where MAX is the maximum value of Ai in the input array and ‘Q’ is the number of queries and N is the size of the array. 


 

We spend MAX * log(MAX) time for a pre-computation part for calculating the prime factors and O(N) time for finding the result of each query.

Space Complexity

O(MAX),where MAX is the maximum value of Ai in the input array .

O(MAX), Since we are storing the reduced form for each number from 1 to MAX and to maintain the count array.


 

Code Solution
(100% EXP penalty)
Co-prime Twins
Full screen
Console