Co-Prime Twins Problem in Java
If both a and b, for all positive integers x, are co-prime to x or both and are not co-prime to x, then the pair of positive integers (a, b) is called a coprime-twin pair. Formally, if and only if S(a) = S(b), where S(x) represents the set of all positive integers that are co-prime to x, then two separate positive integers, a and b, can form a coprime-twin pair.
Example 1:
Input:
int(a, b) = (3, 5)
Output:
The numbers are Co-prime twin numbers.
Explanation:
The given numbers are co-prime with 1. Hence, it is called a Co-prime twin number.
A sequence of indices (i, j) that have i < j and a pair (ai, aj) that forms a coprime-twin pair is said to have a score of a1, a2,... an. Two sets of queries (A and Q) of the format L and R are given to us. The score of the subarray [L, R] inclusive should be determined for each query.
Note: A continuous, non-empty part of the array is called a subarray.
Approach: Brute Force Simulation
If and only if all of the primes in the prime factorization of two numbers are equivalent, they are referred to as co-prime twins. Therefore, in order to compare the sets, we must decrease any power of a prime to a single for any given integer.
We can simplify x = p1 * p2 * p,.. pk to x = p1^x1*p2^x2 … pk^xk.
This can now be performed by pre-calculating primes using an Eratosthenes sieve. All that is required is to count the number of equal pairs in that range for each query, which can be accomplished using a count array.
Algorithm:
coprimeTwins (Q, A) returns the answer for each of the queries in Q.
Step 1: To determine each number's reduced form between 1 and MAX, call the pre-computation function.
Step 2: Change every element in the array to its most basic form.
Step 3: At this point, R iterates from L to R for each inquiry L, increasing the response by cnt[arr[i]] and increasing it by 1.
Step 4: Ultimately, return the Count array to zero.
precompute(reduced) generates an array containing the reduced form of each index.
To determine whether reduced[i] = 1 (a prime number), we run a sieve from 1 to MAX. If so, we loop over all of its multiples and multiply reduced[j] by i.
Implementation:
FileName: BruteForce.java
import java.util.Arrays;
public class BruteForce
{
static void PreComputation(int[] reduce)
{
final int max = (int) 1e6;
// Using a sieve, calculate the reduced form
for (int i = 2; i <= max; i++)
{
// based on this i is a prime
if (reduce[i] == 1)
{
// Add i to all its multiples
for (int j = i; j <= max; j += i)
reduce[j] *= i;
}
}
}
public static int[] CoPrimeTwinNumbers(int[] arr, int[][] query)
{
final int max = (int) 1e6;
// An array for the reduced form
int[] reduce = new int[max + 1];
Arrays.fill(reduce, 1);
// Use a sieve to precompute the reduced form.
PreComputation(reduce);
for (int i = 0; i < arr.length; i++)
{
arr[i] = reduce[arr[i]];
}
// Keep a record of each number's frequency.
int[] count = new int[max + 1];
// To keep track of every query's response.
int[] ans = new int[query.length];
for (int i = 0; i < query.length; i++)
{
int l = query[i][0] - 1, r = query[i][1] - 1;
// To compute the answer, iterate from L to R.
for (int j = l; j <= r; j++)
{
ans[i] += count[arr[j]];
count[arr[j]]++;
}
// Make the count explicit for a new inquiry.
for (int j = l; j <= r; j++)
{
count[arr[j]] = 0;
}
}
return ans;
}
public static void main(String[] args)
{
int[] Array = {2, 4, 6, 8, 6, 4};
int[][] Query = {{3, 5}, {2, 4}, {1, 4}, {1, 5}};
int[] res = CoPrimeTwinNumbers(Array, Query);
System.out.println("The output for the given queries: ");
for (int i = 0; i < res.length; ++i)
{
System.out.println("Query " + (i + 1) + ": " + res[i]);
}
}
}
Output:
The output for the given queries:
Query 1: 1
Query 2: 1
Query 3: 3
Query 4: 4
Complexity Analysis:
The time complexity is O(MAX*log(MAX) + Q*N), where N is the array's size, 'Q' is the number of queries, and MAX is the maximum value of 'i' in the input array. The complexity for each query is O(N).
The maximum value of 'i' in the input array, MAX, determines the space complexity, which is O(MAX). To preserve the count array, we store the reduced version of every integer from 1 to MAX.
Approach: Using Mos Algorithm
We will reduce the numbers to only one power of each prime using the concept from approach 1. Next, we attempt to answer every query in the sequence specified by Mo's algorithm rather than responding to each one as it is submitted.
Let's say we would like to extend the interval's length from [L, R] to [L, R + 1]. In order to allow for the large number of additional pairs that will be added, we increase the count of responses by count[arr[R + 1]]. To reduce the interval, we use a comparable approach.
Algorithm:
coprimeTwins (Q, A) returns the answer for each of the queries in Q.
Step 1: To determine each number's reduced form from 1 to MAX, call the pre-computation function.
Step 2: Change every element in the array to its most basic form.
Step 3: Applying Mo's algorithm, order each query.
Step 4: Repeat over all of the questions from 1 to Q, using the add and remove functions to increase and decrease the interval.
Step 5: Keep the answers to all of our queries in the answer array.
Step 6: Give back the array of answers.
precompute(reduced) yields an array containing the reduced form of each index.
In order to determine whether reduced[i] == 1 (a prime number), we run a sieve from 1 to MAX. Therefore, we loop over all of its multiples and multiply reduced[j] by i.
Implementation:
FileName: CoprimeTwinsMosAlgorithm.java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
class PrimeTwin
{
int ans;
}
class Queries
{
int first;
int second;
int index;
Queries(int first, int second, int index)
{
this.first = first;
this.second = second;
this.index = index;
}
}
public class CoprimeTwinsMosAlgorithm
{
// Function to determine each number's reduced form from 1 to max.
static void preCompute(int[] reduce)
{
final int max = (int) 1e6;
// Use a sieve to calculate the reduced form.
for (int i = 2; i <= max; i++)
{
// based on this i is a prime
if (reduce[i] == 1)
{
// Increase each multiple of i by 1.
for (int j = i; j <= max; j += i)
reduce[j] *= i;
}
}
}
// Add an element to our range with this function.
static void add(int i, int[] count, int[] arr, PrimeTwin x)
{
x.ans += count[arr[i]];
count[arr[i]]++;
}
// Remove an element from our range using this function.
static void remove(int i, int[] count, int[] arr, PrimeTwin x)
{
count[arr[i]]--;
x.ans -= count[arr[i]];
}
public static int[] CoPrimeTwinNumbers(int[] arr, int[][] queries) {
final int max = (int) 1e6;
// An array for the reduced form's storage.
int[] reduce = new int[max + 1];
Arrays.fill(reduce, 1);
// Use a sieve to precompute the reduced form.
preCompute(reduce);
for (int i = 0; i < arr.length; i++)
{
arr[i] = reduce[arr[i]];
}
ArrayList<Queries> q = new ArrayList<Queries>();
for (int i = 0; i < queries.length; i++)
{
q.add(new Queries(queries[i][0], queries[i][1], i));
}
// sqrt(N) is the block size set.
int block = (int) Math.sqrt(arr.length);
// Arrange the list in the order determined by Mo's algorithm.
Collections.sort(q, new Comparator<Queries>()
{
public int compare(Queries x, Queries y)
{
if (x.first / block != y.first / block)
return (x.first < y.first ? -1 : 1);
return (x.second < y.second ? -1 : 1);
}
});
// Keep count of each number's frequency.
int[] count = new int[max+ 1];
// To keep records of each query's response.
int[] ans = new int[queries.length];
PrimeTwin answer = new PrimeTwin();
add(0, count, arr, answer);
int left = 0, right = 0;
for (int i = 0; i < q.size(); i++)
{
int l = q.get(i).first - 1, r = q.get(i).second - 1, index = q.get(i).index;
// Modify the indices to correspond with the current interval.
while (left > l)
{
add(--left, count, arr, answer);
}
while (right < r)
{
add(++right, count, arr, answer);
}
while (left < l)
{
remove(left++, count, arr, answer);
}
while (right > r)
{
remove(right--, count, arr, answer);
}
ans[index] = answer.ans;
}
return ans;
}
public static void main(String[] args)
{
int[] Array = {2, 4, 6, 8, 6, 4};
int[][] Query = {{3, 5}, {2, 4}, {1, 4}, {1, 5}};
int[] res = CoPrimeTwinNumbers(Array, Query);
System.out.println("The output for the given queries: ");
for (int i = 0; i < res.length; ++i)
{
System.out.println("Query " + (i + 1) + ": " + res[i]);
}
}
}
Output:
The output for the given queries:
Query 1: 1
Query 2: 1
Query 3: 3
Query 4: 4
Complexity Analysis:
O(MAX*log(MAX) + (N + Q)*sqrt(N)) is the time complexity, where MAX is the input array's maximum value of AI, 'Q' denotes the number of queries, and N is the array's size. We use O((N + Q)*sqrt(N)) time for Mo's algorithm and MAX * log(MAX) time for the pre-computation portion that determines the prime factors.
O(MAX + Q) is the space complexity, where MAX is the input array's maximum value of AI, "Q" is the number of queries, and "N" is the array's size.