All Tracks Data Structures Arrays 1-D Problem

Pairs Having Similar Elements
Tag(s):

Arrays, Data Structures, Easy, One-dimensional

Problem
Editorial
Analytics

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<j \) and \(A_i\) is similar to \(A_j\).

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<j \) and \(A_i\) is similar to \(A_j\) in a single line.

Constraints

\( 1 \le N \le 10^6\\ 10^{-9} \le A_i \le 10^9 \)

SAMPLE INPUT
8
1 3 5 7 8 2 5 7
SAMPLE OUTPUT
6
Explanation

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.

 

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

Bosch Center for Artificial Intelligence

Challenge Name

Bosch DevOps Hiring challenge

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?