HSH05 - 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. Your task is to do it in O(N) time complexity using Hash array.

Approach:

1. Hash Array Initialization:

  • Initialize a hash array Hash of size 10,001 (to cover all possible values of A[i] from 1 to 10,001) to count occurrences of each number.

2. Counting Beautiful Pairs:

  • Iterate through each element of the array:
  • For each element A[i], calculate its square A[i] * A[i].
  • Check if this square is less than the maximum size of the hash array (to prevent overflow).
  • If it is present, add the count of occurrences of A[i]^2 from the hash array to the result.
  • Update the hash array with the current element A[i].

Complexity:

  • Time Complexity: O(N) Iterate through the whole array to compute the hash.
  • Space Complexity: O(M), M is the size of the hash array declared. Here we have used the hash size of 10^4. So space complexity will be O(M)-> O(10^4).