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 seperated 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.
Link to the problem statement is:: https://www.interviewstreet.com/challenges/dashboard/#problem/4f7272a8b9d15
I coded this problem in java, however all the test cases were not passed....
//This is the Unfriendly Numbers program
import java.io.*;
import java.util.*;
public class unfriendly
{
static int n,k;
static int arr[]=new int[1000000];
static int div[]=new int[1000000];
static int c=0,f=0;
public static void main(String args[])
{
String s1="",s2="";
int j=0;
Scanner sc=new Scanner(System.in);
BufferedReader obj=new BufferedReader(new InputStreamReader(System.in));
String str=sc.nextLine();
for(int h=0;h<str.length();h++)
{
if(str.charAt(h)==' '){
s1=str.substring(0,h);
s2=str.substring(h+1);
}
}
n=Integer.parseInt(s1);
k=Integer.parseInt(s2);
String str1=sc.nextLine();
ArrayList<String> arr2=new ArrayList<String>();
for(String substring: str1.split(" "))
{
arr2.add(substring);
}
ArrayList<Integer> numbers = new ArrayList<Integer>();
for(int i = 0; i < arr2.size(); i++) {
numbers.add(Integer.parseInt(arr2.get(i)));
}
divisor(k);
int ch=0;
for(int y=0;y<f;y++)
{
for(int z=0;z<numbers.size();z++)
{
if(numbers.get(z)%div[y]==0)
ch++;
}
if(ch!=0)
ch=0;
else
c++;
}
System.out.println(c);
}
public static void divisor(int x)
{
//This is a function to form a set/array of divisor elements of a particular number
for(int i=1;i<=x;i++)
{
if(x%i==0)
{
div[f]=i;
f=f+1;
}
}
}
}
import java.io.*;
import java.util.*;
public class unfriendly
{
static int n,k;
static int arr[]=new int[1000000];
static int div[]=new int[1000000];
static int c=0,f=0;
public static void main(String args[])
{
String s1="",s2="";
int j=0;
Scanner sc=new Scanner(System.in);
BufferedReader obj=new BufferedReader(new InputStreamReader(System.in));
String str=sc.nextLine();
for(int h=0;h<str.length();h++)
{
if(str.charAt(h)==' '){
s1=str.substring(0,h);
s2=str.substring(h+1);
}
}
n=Integer.parseInt(s1);
k=Integer.parseInt(s2);
String str1=sc.nextLine();
ArrayList<String> arr2=new ArrayList<String>();
for(String substring: str1.split(" "))
{
arr2.add(substring);
}
ArrayList<Integer> numbers = new ArrayList<Integer>();
for(int i = 0; i < arr2.size(); i++) {
numbers.add(Integer.parseInt(arr2.get(i)));
}
divisor(k);
int ch=0;
for(int y=0;y<f;y++)
{
for(int z=0;z<numbers.size();z++)
{
if(numbers.get(z)%div[y]==0)
ch++;
}
if(ch!=0)
ch=0;
else
c++;
}
System.out.println(c);
}
public static void divisor(int x)
{
//This is a function to form a set/array of divisor elements of a particular number
for(int i=1;i<=x;i++)
{
if(x%i==0)
{
div[f]=i;
f=f+1;
}
}
}
}
0 comments:
Post a Comment