HackerRank Combinatorics – Sherlock and Pairs

Challenge: Sherlock and Pairs

Subdomeniu: Combinatorics (combinatorics)

Scor cont: 30.0 / 30

Submission status: Accepted

Submission score: 1.0

Submission ID: 464726908

Limbaj: python3

Link challenge: https://www.hackerrank.com/challenges/sherlock-and-pairs/problem

Cerinta

Sherlock is given an array of $N$ integers ($A$<sub>$0$</sub>, $A$<sub>$1$</sub> ... $A$<sub>$N-1$</sub> by Watson. Now Watson asks Sherlock how many different pairs of indices $i$ and $j$ exist such that $i$ is not equal to $j$ but $A$<sub>$i$</sub> is equal to $A$<sub>$j$</sub>.     

That is, Sherlock has to count the total number of pairs of indices $(i, j)$ where  $A$<sub>$i$</sub> $= A$<sub>$j$</sub> AND $i ≠ j$.

**Input Format**   
The first line contains $T$, the number of test cases. $T$ test cases follow.   
Each test case consists of two lines; the first line contains an integer $N$, the size of array, while the next line contains $N$ space separated integers.

**Output Format**   
For each test case, print the required answer on a different line. 

**Constraints**   
$1 \le T \le 10$   
$1 \le N \le 10$<sup>$5$</sup>    
$1 \le A[i] \le 10$<sup>$6$</sup>  

**Sample input**

    2
    3
    1 2 3
    3
    1 1 2
    
**Sample output**   

    0
    2
    
**Explanation**   
In the first test case, no two pair of indices exist which satisfy the given condition.   
In the second test case as _A[0] = A[1] = 1_, the pairs of indices _(0,1)_ and _(1,0)_ satisfy the given condition.

Cod sursa

#!/bin/python3

import math
import os
import random
import re
import sys

def solve(a):
    # Write your code here
    a_dic = {}
    pairs = 0
    #loop to count the number of elements
    for i in range(len(a)):
        if a[i] not in a_dic:
            a_dic[a[i]] = 0 #{a[i]:0}
        a_dic[a[i]] += 1 #{a[i]:+1} add one
    #loop for check whats integers taht are more than once
    for k in a_dic:
        val = a_dic[k]
        if val > 1: #condition more than once
            pairs += val * (val-1)  #possible pairs n*(n-1)
    return pairs
if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    t = int(input().strip())

    for t_itr in range(t):
        a_count = int(input().strip())

        a = list(map(int, input().rstrip().split()))

        result = solve(a)

        fptr.write(str(result) + '\n')

    fptr.close()