Last Updated: 11 Nov, 2021
Twin Pairs
Easy
Asked in company
Bob always bragged about his smartness. To test this, Alice gave him an
array ‘A’ of size ‘N’ and asked him to find the number of twin pairs in that array.
A twin pair can be defined as a pair of indexes ‘x’, ‘y’ such that ‘x’ is less than ‘y’ and ‘A[y]’ - ‘A[x]’ = ‘y’ - ‘x’.
Bob was having a hard time doing so, so he asked you to help him find the total number of twin pairs.
Input Format:
The first line of input contains an integer ‘T’, denoting the number of test cases.
The first line of each test case contains two spaced integers, ‘N’ denoting the size of the array.
The following line contains an array ‘A’ of ‘N’ spaced integers.
Output Format:
For each test case, print a single integer denoting the number of twin pairs in the array.
Note:
You are not required to print the expected output. It has already been taken care of. Just implement the function.
Constraints:
1 <= T <= 5
1 <= N <= 10^5
1 <= A[i] <= N
Time Limit: 1 sec
Approaches
We can check all the pairs of indexes using two nested loops and if they satisfy the given constraints, then increase the count of twin pairs by 1.
Algorithm:
- Initialise ‘ans’ to 0.
- Run a loop ‘i’ from 0 to ‘N’ - 1
- Run a loop ‘j’ from ‘i’ + 1 to ‘N’ - 1
- If ‘A[j]’ - ‘A[i]’ equals ‘j’ - ‘i’, increase ‘ans’ by one.
- Run a loop ‘j’ from ‘i’ + 1 to ‘N’ - 1
- Return ‘ans’.
We are given that two indexes, ‘x’ and ‘y’ are twin pairs when:
- ‘x’ < ‘y’
- ‘A[y]’ - ‘A[x]’ = ‘y’ - ‘x’
If we rearrange the second condition we get:
‘A[y]’ - y = ‘A[x]’ - ‘x’
Now let ‘B[i]’ be equal to ‘A[i]’ - ‘i’, so the new condition for ‘x’ and ‘y’ to be a twin pair becomes:
- ‘x’ < ‘y’
- ‘B[x]’ = ‘B[y]’
We can use the map to store the frequency of all the values of ‘B[x]’ till ‘y’ and the frequency of ‘B[y]’ is in the map will give us the count of twin pairs index ‘y’ with all the indexes less than ‘y’.
Algorithm:
- Initialise ‘ans’ to 0.
- Declare a map ‘cn’ from int to int.
- Run a loop ‘i’ from 0 to ‘N’ - 1
- Initialize b to ‘A[i]’ - (i + 1).
- Add ‘cn[b]’ to ‘ans’.
- Increment ‘cn[b]’.
- Return ‘ans’.