PROBLEM LINK:
Author: Md Shahid
Tester: Soham Chakrabarti
Editorialist: Md Shahid
DIFFICULTY:
Easy
PREREQUISITES:
Math, GCD and LCM
PROBLEM:
Given an array A, you need to calculate number of pairs which satisfied the following conditions :
- LCM(A_i, A_j) = 2*GCD(A_i, A_j), where 1\leq i \leq N and 1\leq j \leq N
- (A_i, A_j) = (A_j, A_i)
QUICK EXPLANATION:
If you observe carefully then you will notice that, LCM(A_i, A_j) = 2*GCD(A_i, A_j) is only possible when A_i = 2*A_j or A_j = 2*A_i . As second condition says that (A_i, A_j) = (A_j, A_i) which means there will be only one pair possible when A_i = 2*A_j or A_j = 2*A_i.
EXPLANATION:
The mathematical explanation is as follows :
=>LCM(A_i, A_j) = 2*GCD(A_i, A_j)---(1)
As LCM(A_i, A_j) = \frac{(A_i *A_j)}{GCD(A_i,A_J)}
From (1), \frac{(A_i *A_j)}{GCD(A_i,A_J)} = 2*GCD(A_i, A_j)
=> A_i * A_j = 2*GCD(A_i, A_j) *GCD(A_i, A_j)---(2)
As we all know that GCD(A_i, A_j) must divide both A_i and A_j perfectly i.e,
A_i = C_{i}*GCD(A_i,A_j)---(3)
A_j = C_{j}*GCD(A_i,A_j)---(4)
where C_{i}\geq1 and C_j\geq1 are integers constant for A_i and A_j.
Now, substitute the values of A_i and A_j in equation (2) then we get,
C_i * C_j = 2
As C_i and C_j cannot be fraction then either C_i =1 and C_j=2 or C_i =2 and C_j=1
If you put the values of C_i and C_j in equations (3) and (4), then you will get either
A_i = 2*A_j or A_j = 2*A_i.
Time Complexity : O(n)
SOLUTIONS LINKS:
Author's Solution
for _ in range(int(input())):
n = int(input())
A = [int(x) for x in input().split()]
d = {}
cnt = 0
for i in A:
if i in d:
d[i]+=1
else:
d[i] = 1
for i in d:
if i*2 in d:
cnt += d[i]*d[i*2]
print(cnt)
Tester's Solution
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
int main(){
ll T;
cin>>T;
while(T--) {
ll n, cnt=0;
cin>>n;
ll A[n];
for(ll i=0; i<n; i++) cin>>A[i];
unordered_map<int, int> freq;
for(ll i=0; i<n; i++){
freq[A[i]]++;
}
for( auto x : freq){
ll y = x.first;
if(freq.find(2*y)!=freq.end())
cnt+= freq[y]*freq[2*y];
}
cout<<cnt<<endl;
}
return 0;
}
If you have better approach, please do not hesitate to share with us. All the suggestions are welcome.