HSH02 - 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, 1≤i<j≤N. Count the number of Beautiful Pairs in the given array.

Approach:

  • It uses a nested loop structure to examine each unique pair of elements in the array.
  • For each pair (i,j), it checks whether the condition A[i] = A[j]^2 holds.
  • Each time the condition is satisfied, a counter is incremented to keep track of the number of Beautiful Pairs found.

Complexity:

  • Time Complexity: O(N^2) We are using two nested loops.
  • Space Complexity: O(1) No extra space is used.