Twin Pairs

Easy
0/40
Average time to solve is 15m
profile
Contributed by
1 upvote
Asked in company
TCS

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
4 
1 1 4 3
2 
2 1
Sample Output 1:
1
0
Explanation for Sample Input 1:
In the first test case, only indexes 2 and 4 form a twin pair as 3 - 2 = 4 - 2. So the total number of twin pairs in the array is 1.

In the second test case, no twin pair exists in the array, so the total count is 0.
Sample Input 2:
2
5 
1 2 3 4 5
3 
2 2 2
Sample Output 2:
10 
0
Hint

Can we check all pairs and count the total number of twin pairs?

Approaches (2)
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’.
Time Complexity

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


 

Space Complexity

O(1)

We are using constant extra space.


 

Code Solution
(100% EXP penalty)
Twin Pairs
Full screen
Console