Twin Pairs
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

Question

Twin Pairs

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

Accepted Answer

Brute Force

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.

Return ‘ans’.

Space Complexity: O(1)Explanation:

O(1)

We are using constant extra space.

Time Complexity: O(n^2)Explanation:

O(N ^ 2), where ‘N’ is the length of the given array.

Since we use two nested loops to find all possible pairs of indexes, the total time complexity becomes O(N * N).

C++ (g++ 5.4)

/*
    Time Complexity: O(N ^ 2)
    Space Complexity: O(1)

    Where ‘N’ is the length of the given array.
*/

long long int twinPairs(vector A)
{
    long long int ans = 0;
    int n = A.size();

    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {   
            // Checking if twin pairs or not.
            if (A[j] - A[i] == j - i)
            {
                ans++;
            }
        }
    }

    return ans;

}

Python (3.5)

'''

    Time Complexity: O(N ^ 2)

    Space Complexity: O(1)



    Where ‘N’ is the length of the given array.

'''



def twinPairs(A):

    

    n = len(A)

    

    # Creating variable to keep answer.

    ans = 0

    

    for i in range (n):

        

        for j in range (i + 1, n):

            # Checking if twin pairs or not.

            if A[j] - A[i] == j - i:

                ans += 1

        

    return ans

Java (SE 1.8)

/*

    Time Complexity: O(N ^ 2)

    Space Complexity: O(1)



    Where N is the length of the given array.

*/



public class Solution {



    public static long twinPairs(int[] A) {



        long ans = 0;

        int n = A.length;



        for (int i = 0; i < n; i++)

        {

            for (int j = i + 1; j < n; j++)

            {   

                // Checking if twin pairs or not.

                if (A[j] - A[i] == j - i)

                {

                    ans++;

                }

            }

        }



        return ans;

    }

}

Accepted Answer

Maths

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’.

Space Complexity: O(n)Explanation:

O(N), where ‘N’ is the length of the given array.

We will store the frequency in the map, which will take O(N) space.

Time Complexity: O(n)Explanation: