Pairs

Back

Problem

You will be given an array of integers and a target value. Determine the number of pairs of array elements that have a difference equal to a target value.

For example, given an array of [1, 2, 3, 4] and a target value of 1, we have three values meeting the condition: 2 - 1 = 1, 3 - 2 = 1, and 4 - 3 = 1.

Function Description

Complete the pairs function below. It must return an integer representing the number of element pairs having the required difference.

pairs has the following parameter(s):

  • k: an integer, the target difference
  • arr: an array of integers

Input Format

The first line contains two space-separated integers n and k, the size of arr and the target value.
The second line contains n space-separated integers of the array arr.

Constraints

  • 2 ≤ n ≤ 105
  • 0 < k < 109
  • 0 < arr[i] < 231 - 1
  • each integer arr[i] will be unique

Output Format

An integer representing the number of pairs of integers whose difference is k.

Solution


// Complete the pairs function below.
static int pairs(int k, int[] arr) {
	int pairs = 0;
	
	Array.Sort(arr);
	
	int start = 1;
	for (int i = 0; i < arr.Length-1; i++)
	{
		for (int j = start; j < arr.Length; j++)
		{
			if (arr[j] - arr[i] > k) break;
			if (arr[j] - arr[i] == k)
			{
				pairs++;
				start = j+1;
				break;
			}
			start = i + 2;
		}
	}
	
	return pairs;
}
			

Top