Given a 1-indexed array A of size N, the distance between any 2 indices of this array i and j is given by |i−j|. Now, given this information, I need to find for every index i (1≤i≤N), an index j, such that 1≤j≤N, i≠j, and GCD(A[i],A[j])>1.
If there are multiple such candidates for an index i, have to find index j, such that the distance between i and j is minimal. If there still exist multiple candidates, print the minimum j satisfying the above constraints.
Example: Array(A) 2 3 4 9 17
Output : 3 4 1 2 -1
Note: array size can be as large as 2*10^5. and each array element can take max value 2*10^5 and min value 1.
I should be able to calculate this in 1 second at most.
Here is my code, but its exceeding time limit. Is there a way to optimize it.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class GCD {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine().trim());
int[] a = new int[n+1];
StringBuilder sb =new StringBuilder("");
String[] array = br.readLine().trim().split(" ");
for(int i=1; i<=n; i++){
a[i] = Integer.parseInt(array[i-1]);
}
int c,d;
l1: for(int i=1; i<=n; i++){
c = i-1;
d = i+1;
while((c>0||d<=n)){
if(c>0){
if(GCD(a[i],a[c])>1){
sb.append(c+" ");
continue l1;
}
}
if(d<=n){
if(GCD(a[i],a[d])>1){
sb.append(d+" ");
continue l1;
}
}
c--;
d++;
}
sb.append("-1 ");
}
System.out.println(sb);
}
static long GCD(int a, int b){
if(b==0)
return a;
return GCD(b, a%b);
}
}
You know the problem can be solved in one second. You know that array can have 200,000 elements. Comparing 200,000 elements with 200,000 elements takes 40 billion comparisons. If you're lucky your computer does 3 billion operations per second. You see that comparing 200,000 elements with 200,000 elements isn't going to work. (That would happen in the simple case where all array elements are equal to 1). So optimizing your code isn't going to help.
So move your mind away from the way the problem is posed. It asks to find j so that gcd (a [i], a [j]) != 1. What it really means is to find j so that a [j] has a prime factor in common with a [i]. And that j needs to be the largest j < i or the smallest j > i.
The numbers are small, less than 200,000. So you can find all the different prime factors of a a [i] very quickly.
So first you create an array "index": For each prime number p <= 200,000, index [p] is the index j of the last array element a [j] that you examined which had the prime factor p, or -1 if you didn't find any. You also create an array "solution": For each i that you examined, it contains the closest number so far or -1.
Iterate through the array for i = 1 to n: For each a [i], find all prime factors. For every factor p: If j = index [p] > 0 then a [j] is also divisible by p, so gcd (a [i], a [j]) > 1. Doing that you get the largest j < i with gcd (a [i], a [j]) > 1. Also update the array index as you find prime factors.
But also if you find that a [i] and a [j] have a common factor, then the solution that you stored for j might be wrong because it only considered indices less than j, so update solution as well. Pseudo-code:
Create array "index" filled with -1.
Create array "solution" filled with -1.
for all i
for all prime factors p of a [i]
let j = index [p]
index [p] = j
if j >= 0
if solution [i] = -1
solution [i] = j
else if j > solution [i]
solution [i] = j
if solution [j] = -1
solution [j] = i
else if solution [j] < j && i-j < j - solution [j]
solution [j] = i
print solution
You can see it doesn't matter at all how far the array element with a common factor is away. The execution time is a very small number times the number of prime factors, plus the time for finding the factors, which is worst if all elements are large primes. So all you need to do is find all the factors of any number < 200,000 in say 3-4 microseconds. Should be easy. You are allowed to create a table of prime numbers up to 500 before you start.