Software Development

# Depend distinct pair of indices in Array whose GCD and LCM are similar

Given an array A[] of size N, the duty is to search out the whole variety of distinct pairs (i, j) of indices the place 1 ≤ i < j ≤ N such that the best widespread divisor(gcd) and least widespread a number of(lcm) of those components are equal.

Examples:

Enter: A[] = {2, 5, 5, 5, 6}
Output:
Clarification: Right here pair (i, j) are: (2, 3), (3, 4), and (2, 4).
To elaborate, gcd(A2, A3) = lcm(A2, A3) = 5.

Enter: A[] = {22, 22, 38, 38}
Output: 2

Method: The issue could be solved based mostly on the next remark:

Observations:

• The remark to be made right here is as follows: gcd(Ai, Aj) = lcm(Ai, Aj)⟺ Ai = Aj
• So, the issue reduces to easily counting the variety of pairs of equal components in A.
• Construct a frequency map of the weather of A (utilizing map/unordered_map in C++, TreeMap/Hashmap in Java, or dict in python) after which iterate throughout its components.
• If a component x has a frequency of fx, then it contributes fx⋅(fx−1)/2 pairs to the reply, so sum this worth throughout all x.

Observe the beneath steps to resolve the issue:

• Declare a hash map.
• Begin iterating over the whole array
• If the factor is current within the map, then enhance the worth of frequency by 1.
• In any other case, insert that factor into the map.
• After that begin traversing the map and get the worth(frequency of factor).
• If a component x has a frequency of fx, then it contributes fx⋅(fx − 1) / 2 pairs to the reply, so sum this worth throughout all x.

Beneath is the implementation of the above method:

## Java

 `import` `java.io.*;``import` `java.util.*;`` ` `public` `class` `GFG {``    ``    ``    ``public` `static` `lengthy` `pairCount(``int` `a[], ``int` `n)``    ``{``        ``Map mp = ``new` `HashMap<>();``        ``for` `(``int` `i = ``0``; i < n; i++) {``            ``if` `(mp.containsKey(a[i])) {``                ``mp.put(a[i], mp.get(a[i]) + ``1``);``            ``}``            ``else` `{``                ``mp.put(a[i], ``1``);``            ``}``        ``}``        ``lengthy` `ans = ``0``;``        ``for` `(``int` `i : mp.values()) {``            ``ans += (``lengthy``)i * (``lengthy``)(i - ``1``) / ``2``;``        ``}``        ``return` `ans;``    ``}`` ` `    ``    ``public` `static` `void` `primary(String[] args)``    ``{``        ``int` `A[] = { ``2``, ``5``, ``5``, ``5``, ``6` `};``        ``int` `N = A.size;`` ` `        ``        ``System.out.println(pairCount(A, N));``    ``}``}`

Time Complexity: O(N)
Auxiliary Area: O(1)