Question

java

Write a program to determine the number pairs of values in an input file that are equal. If your first try is quadratic, think again and use Arrays.sort() to develop a linearithmic solution.

Answer 1

import java.io.*;
import java.util.*;
public class DuplicatePairs
{
public static void main(String[] args)throws Exception
{
File file = new File("C:\\Users\\Debjit G\\Desktop\\test.txt");
BufferedReader br = new BufferedReader(new FileReader(file)); //Loading the required file into BufferedReader
String st=br.readLine(); //Reading the line of numbers
int n,i,j;
n=0;
for(i=0;i<st.length();i++) //Counting the number of spaces and hence number of integers in the string
{
if(st.charAt(i)==' ')
n++;
}
n=n+1;
int a[]=new int[n];
String w="";
j=0;
for(i=0;i<st.length();i++) //Extracting the integers from the string into an array
{
if(st.charAt(i)==' ')
{
a[j++]=Integer.parseInt(w);
w="";
}
else
w=w+st.charAt(i);
}
a[j++]=Integer.parseInt(w);
Arrays.sort(a); //Sorting the array
j=0;
int count=0,c;
while(j<n) //Counting the frequency of every number in the array and hence finding the number of duplicate pairs
{
c=1;
while(j+1<n && a[j+1]==a[j])
{
c++;
j++;
}
j++;
count=count+(c*(c-1)/2);
}
System.out.println("Number of duplicate pairs in the array : "+count);
}
}

So, we first load the file into the BufferedReader object and read the line of integers from the file. Then we count the number of spaces to know the number of integers in the string, and create an array of that size. Then we extract the integers into the array one by one. Now we have two choices. We can create every pair in the array and check for duplicates, but that will take Quadratic Time Complexity. So we sort the array and count the frequency of every number in the array. For n same integers in the array, nC2 number of pairs will be formed. Now nC2 can also be written as n*(n-1)/2, which we use in the code. We output the result stored in count, and the Time Complexity is Linear.