HACKING THE RANDOM NUMBER GENERATOR

SPOJ Problem Set (classical)

9734. Hacking the random number generator

Problem code: HACKRNDM



You recently wrote a random number generator code for a web application and now you notice that some cracker has cracked it. It now gives numbers at a difference of some given value k more predominantly. You being a hacker decide to write a code that will take in n numbers as input and a value k and find the total number of pairs of numbers whose absolute difference is equal to k, in order to assist you in your random number generator testing.

NOTE: All values fit in the range of a signed integer, n,k>=1

Input

1st line contains n & k.
2nd line contains n numbers of the set. All the n numbers are assured to be distinct.

Output

One integer saying the no of pairs of numbers that have a diff k.

Example

Input:
5 2
1 5 3 4 2

Output:
3

SOLUTION-----

#include
#include
using namespace std;
int main()
{
    signed int n,k,count=0,i;
    scanf("%u %u",&n,&k);
    signed int arr[n];
    for(i=0;i<n;i++)
        scanf("%u",&arr[i]);
    sort(arr,arr+n);
    for(i=0;i<n;i++)
    {
        int flag=0,mid;
        //binary search//
        int lb=0,ub=n-1;
        while(lb<=ub)
        {
            mid=(lb+ub)/2;
            if(arr[mid]==arr[i]+k)
            {
                flag=1;
                break;
            }
            else if(arr[mid]>arr[i]+k)
                ub=mid-1;
            else
                lb=mid+1;
        }
        if(flag==1)
            count+=1;
    }
    printf("%u\n",count);
    return 0;
}