Problem | Find the number of pairs in an array whose subtraction is x

Question

Consider an array with distinct integers in it.

Example : { 1 , 5 , 4 ,8 , 9 } , Say , x = 4

Then , the output will be 3 { (9-5) , (5-1) and (8-4) }.

Find number of pairs (i,j) , such that j>i and a[j]-a[i] = x .

Write answer in two sets :-

1)Explanation.

2)Code.

Answer 1

Given Problem:
nums = { 1 , 5 , 4 ,8 , 9 }
Target = 4
equation : nums[j] - nums[i] = target where (j > i)

Counts = 3 = { {9-5} , {8-4} , {5-1} }

Explanation :
Lets re-write the equation as
nums[j] - nums[i] = target;
nums[i] = nums[j] - target
now assume we are at some integer let it be '8'. What information do we need ? 

we need to know what all integers towards left of us can form pair with '8' as nums[j] - nums[I] = target, here nums[j] = 8

• lets calculate need = nums[j] - target
• now we can pair up with all the number having the value as "need" and which are towards left hand side.
• we need count of the "need" that are towards left of us
• we can store count of numbers using a map storing key-value pair  where KEY = num and VALUE = frequency so far

ALGORITHM:

1. declare an unordered map, aka hashmap, lets call it as frequency
2. declare count, this will be storing count of pairs which meets up the above equation
3. for num in nums
4. calculate the need = num - target
5. add number of times we have seen the number "need" ; count += frequency[need]
6. increase frequency[num] as now we have seen this number and would be moving towards right side.
7. repeat from 3 till you traverse the entire nums array

CODE:
int getPairsCount(vector<int> &nums, int target)
{
    unordered_map<int,int> frequency;
    int counts = 0;
    for(auto num : nums)
    {
        // given equation can be re written as
        // aj - ai = t
        // ai = aj - t;
        int need = num - target;
        counts += frequency[need];
        frequency[num]++;
    }
    return counts;
}

Keep learning, Thanks for reading out.

Comments

Awesome answer man!