InterviewStreet unfriendly numbers java

Question

For more information about this question, please look here: https://www.interviewstreet.com/challenges/dashboard/#problem/4f7272a8b9d15

There is one friendly number and N unfriendly numbers. We want to find how many numbers are there which exactly divide the friendly number, but does not divide any of the unfriendly numbers.

Input Format: The first line of input contains two numbers N and K separated by spaces. N is the number of unfriendly numbers, K is the friendly number. The second line of input contains N space separated unfriendly numbers.

Output Format: Output the answer in a single line.

Constraints:

1 <= N <= 10^6

1 <= K <= 10^13

1 <= unfriendly numbers <= 10^18

Sample Input:

8 16

2 5 7 4 3 8 3 18

Sample Output:

1

Explanation : Divisors of the given friendly number 16, are { 1, 2, 4, 8, 16 } and the unfriendly numbers are {2, 5, 7, 4, 3, 8, 3, 18}. Now 1 divides all unfriendly numbers, 2 divide 2, 4 divide 4, 8 divide 8 but 16 divides none of them. So only one number exists which divide the friendly number but does not divide any of the unfriendly numbers. So the answer is 1.

Many people asked this question but no perfect answer has been given. This is not a duplicate as others are closed, I got to ask this question

I've used Sieve of Eratosthenes to refine unfriendly numbers(remove duplicates, remove unnecessary numbers like 2 & 4 in the given example. numbers which divide 2 & 4 also divide 8, so only 8 wud serve the purpose. After doing all these I removed primes)

Here is my code

import java.io.*;
import java.util.*;

public class unfriendly {
public static ArrayList<Long> refine_unfriendly(ArrayList<Long> uf){
    int n=uf.size();
    long x;
    for(int i=uf.size()-1;i>=0;i--){
        x=uf.get(i);
        for(int j=uf.size()-1;j>=0;j--){
            if(j==i)
                continue;
            if(j!=i && uf.get(j)%x==0){
                x=uf.get(j);
                uf.remove(i);
                break;
            }
            else if(j!=i && x%uf.get(j)==0){
                uf.remove(j);
                break;
            }
        }
    }
    return uf;
}

public static void print_output(long k,ArrayList<Long> uf){
    int n=uf.size(),count=0,i;
    long x,y;
    if(n==0)
        count++;
    for(x=2;x<=Math.sqrt(k);x++){
        if(k%x==0){
            for(i=0;i<n;i++){
                if(uf.get(i)%x==0)
                    break;
            }
            if(i==n)
                count++;
            if(k/x!=x){
                y=k/x;
                for(i=0;i<n;i++){
                    if(uf.get(i)%y==0)
                        break;
                }
                if(i==n)
                    count++;
            }
        }
    }
    for(i=0;i<n;i++){
        if(uf.get(i)%k==0)
            break;
    }
    if(i==n)
        count++;
    System.out.println(count);
}
public static void main(String[] args) throws Exception {
    Scanner in=new Scanner(System.in);
    int n=in.nextInt();
    long k=in.nextLong();
    ArrayList<Long> uf=new ArrayList<Long>();
    for(int i=0;i<n;i++)
        uf.add(in.nextLong());
    uf=refine_unfriendly(uf);
    print_output(k,uf);
}
}

This solves only 1 test case out of 6. Rest are exceeding the time limit. The brute force method (without refining) solved 3 test cases. Someone please help.

Thanks in advance

Answer 1

You just generate all divisors of K (it takes sqrt(K) time) , and you have create a new unique array of GCD(a[i],K), because if divisor of friendly number divides unfriendly number then it has to divide GCD(unfriendly number,K), so you just use set , because GCD(a[i],K) there are nd(K) number where nd(K) stands for the number of divisors of K . So the algorithm takes just O(nd(K)^2) time .

Here is main body of my code :

for(int i=1;i<=n;i++)
    mm.insert(gcd(a[i],k));

vv=(int)sqrt((double)k);

for(int i=1;i<=vv;i++)
    {
        if(k%i==0)
            {
                zz[++cur]=i;
                zz[++cur]=k/i;
            }
    }
if((ll)vv*(ll)vv==k)
    cur--;
int say=0;
for(int i=1;i<=cur;i++)
    {
        q=0;
        for(it=mm.begin();it!=mm.end();it++)
            if(*it%zz[i]==0)
                {
                    q=1;
                    break;
                }
        if(q==0)
            say++;
    }
cout<<say<<endl;