HSH09 - Editorial

editorial
, , ,
1

Problem Link - Count Beautiful Pairs in Hashing

Problem Statement:

You have an array A of N integers. A pair of indices (i,j) is called Beautiful if A_i = A_j^2 and 1≤i<j≤N. Count the number of Beautiful Pairs in the given array.
Note: You have to use the hash function given in the IDE

Approach:

1. Hash Function:

  • A hash function f(x)=x mod M is used to map values to a hash array of size M. Here, M=999983 is a large prime number to minimize collisions in the hash array.

2. Counting Beautiful Pairs:

  • Loop through each element of the array:
    • For each element A[i], check if its square A[i]^2 is less than MX (which is 10^9).
    • If true, look up how many times A[i]^2 has been seen before (i.e., check Hash[f(a_i^2)] to see how many occurrences exist).
    • Increase the count, as it represents the number of pairs that can be formed with the current element.
  • Update the hash array with the current element A[i] by incrementing Hash[f(a[i])]

Complexity:

  • Time Complexity: O(N) due to a single loop through the array.
  • Space Complexity: O(M) Size of hash array