Skip to content

Instantly share code, notes, and snippets.

@gogsbread
Created January 28, 2013 22:30
Show Gist options
  • Save gogsbread/4659876 to your computer and use it in GitHub Desktop.
Save gogsbread/4659876 to your computer and use it in GitHub Desktop.
o(n) algorithm for finding the number of pairs that have a difference of k
using System;
using System.Collections.Generic;
class Solution
{
//Get N and K
// Read N and split.
// scan N array
//create a bucket
//count =0
// if bucket contains n-2 then c++
//if bucket contains n+2 then c++
// add number to bucket.
// 5 2
// 1 5 3 4 2
static void Main()
{
string[] nk = Console.ReadLine().Split(' ');
int n = int.Parse(nk[0]);
int k = int.Parse(nk[1]);
string[] a = Console.ReadLine().Split(' ');
HashSet<int> s = new HashSet<int>();
int count=0;
for (int i = 0; i < n; i++)
{
int e = int.Parse(a[i]);
if (s.Contains(e - k))
count++;
if (s.Contains(e + k))
count++;
s.Add(e);
}
Console.WriteLine(count);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment