InterviewStreet: Pairs

Problem:

For the problem statement, follow the link.

Statement:

Given N numbers , [N<=10^5] we need to count the total pairs of numbers that have a difference of K. [K>0 and K<1e9]

Input Format:
1st line contains N & K (integers).
2nd line contains N numbers of the set. All the N numbers are assured to be distinct.
Output Format:
One integer saying the no of pairs of numbers that have a diff K.

Sample Input #00:
5 2
1 5 3 4 2

Sample Output #00:3

 

Sample Input #01:

10 1

363374326 364147530 61825163 1073065718 1281246024 1399469912 428047635 491595254 879792181 1069262793 

 

Sample Output #01:

0

 

Note: Java/C# code should be in a class named "Solution"

Read input from STDIN and write output to STDOUT. 

Solution:

From the problem statement, we could have N, the number of array, could be as large as 10^5, so our algorithm's up limit is O(nlogn), since usually the time cost scale could be no bigger than 10^7;

After viewing the problem, we know all the numbers are distinct, so we could sort them first, as everybody know, quick-sort or merge-sort could take O(nlogn) time.

So, after sorting, we have an non-decreasing array of numbers, and we need to find the pair which difference is K. Here, we could go through every element, then for each element, we can use binary search to find the other number. So, this will take O(N) to go through array, and O(logN) for using binary search,
Thus, F(N) = f*g = O(N) * O(logN) = O(NlogN).

But some minor bugs could be easily made here,
1st, there could be two distinct number to pair with ith number, and both of pairs' difference could be K. So, we need to search in both direction.
2nd, in binary search, take great care of the boundary case, don't make it infinite, and don't make any blind spot in that search.

Code is as follow:

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

/**
 * 
 */

/**
 * @author antonio081014
 * @time: Oct 6, 2012, 2:32:58 PM
 */
public class Solution {

    private int K;

    /**
     * @param args
     */
    public static void main(String[] args) throws Exception {
 Solution main = new Solution();
 main.run();
 System.exit(0);
    }

    public void run() throws Exception {
 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 String[] str = br.readLine().split("\\s");
 int N = Integer.parseInt(str[0]);
 K = Integer.parseInt(str[1]);
 int[] array = new int[N];
 str = br.readLine().split("\\s");
 for (int i = 0; i < N; i++)
     array[i] = Integer.parseInt(str[i]);

 Arrays.sort(array);
 int count = 0;
 for (int i = 0; i < N; i++) {
     count += binaryLeft(0, i - 1, array, i);
     count += binaryRight(i + 1, N - 1, array, i);
 }
 System.out.println(count / 2);
    }

    private int binaryLeft(int low, int high, int[] array, int index) {
 while (low <= high) {
     int mid = (low + high) / 2;
     if (array[mid] + K == array[index]) {
  // System.out.println("" + array[index] + " " + array[mid]);
  return 1;
     } else if (array[mid] + K < array[index])
  low = mid + 1;
     else
  high = mid - 1;
 }
 return 0;
    }

    private int binaryRight(int low, int high, int[] array, int index) {
 while (low <= high) {
     int mid = (low + high) / 2;
     if (array[mid] - K == array[index]) {
  // System.out.println("" + array[index] + " " + array[mid]);
  return 1;
     } else if (array[mid] - K < array[index])
  low = mid + 1;
     else
  high = mid - 1;
 }
 return 0;
    }
}