Given an array, \(A\), having \(N\) integers \(A_1,A_2,...,A_N\).Two elements of the array \(A_i\) and \(A_j\) are called similar iff \(A_i = A_j+1\) or \(A_j = A_i + 1\) .
Also, the similarity follows transitivity. If \(A_i\) and \(A_j\) are similar and \(A_j\) and \(A_k\) are similar, then \(A_i\) and \(A_k\) are also similar.
Note: \(i\), \(j\), and \(k\) are all distinct.
You need to find number of pairs of indices \((i,j)\) such that \(i
Input
The first line contains a single integer \(N\) denoting number of elements in the array.
The second line contains \(N\) space separated integers where \(i^{th}\) elements indicate\(A_i\).
Output
Output the number of pairs of indices \((i,j)\) such that \(i
Constraints
8 1 3 5 7 8 2 5 7
6
We have \(6\) possible pairs of indices which contain similar elements.
\((1,6)\) : \(A_1\) and \(A_6\) are similar since \(2 = 1 + 1\).
\((2,6)\) : \(A_2\) and \(A_6\) are similar since \(3= 2+1\).
\((1,2)\) : \(A_1\) and \(A_6\) are similar by transitivity since \((A_1,A_6)\) and \((A_2,A_6 )\) are similar, so \(A_1\) and \(A_2\) are also similar.
\((4,5)\) : \(A_4\) and \(A_5\) are similar since \(8 = 7+1\).
\((5,8)\) : \(A_5\) and \(A_8\) are similar since \(8= 7+1\)
\((4,8)\) : \(A_4\) and \(A_8\) are similar by transitivity since \((A_4,A_5)\), \((A_5,A_8)\) are similar, so \(A_4\) and \(A_8\) are also similar.
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor