Problem Statement:
You are given an array A of size N.You have to find the number of quadruplets based on certain condition:
1.A[i]×A[j]=A[k]×A[l]
2.i<j<k<l
Solution:
Bruteforce Approach: Run 4 loops and everytime check the above condition whenever the condition is true simply increment the count value.
TC: O(N^4)
This solution will surely give TLE error but pass some testcases.
Now Efficient Approach Using Hashing
Blue stick method. i=1 j=2; Fix ‘j’. p =
a[i]*a[j]
-> We just need to know how many pairs have product = p in the
range [j+1….N] which can be pre-calculated using hashmap
-> We have calculated all the valid quadruplets whose j = 2;
-> Now calculate all valid quadruplets; whose j = 3.
-> p1 = a1a3; p2 = a2a3;
-> check how many pairs have product = p1 in range [j+1…N]
-> same for p2.
Code:
package hashing;
import java.util.HashMap;
import java.util.Scanner;
public class GoogleOAQuadruplets {
public static int solve(int [] arr,int n) {
int count=0;
HashMap<Integer, Integer> map=new HashMap<Integer, Integer>();
for(int k=3;k<=n;k++) {
for(int l=k+1;l<=n;l++) {
map.put(arr[k]*arr[l], map.getOrDefault(arr[k]*arr[l], 0)+1);
}
}
for(int j=2;j<=n-3;j++) {
for(int i=1;i<=j-1;i++) {
int p=arr[i]*arr[j];
count+=map.getOrDefault(p, 0);
}
//remove the pairs from (j+1,j+2).......(j+1,N)
for(int q=j+2;q<=n;q++) {
int p=arr[j+1]*arr[q];
map.remove(p);
}
}
return count;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int [] arr=new int[n+1];
int i=1;
while(i<=n) {
arr[i]=sc.nextInt();
++i;
}
System.out.println(solve(arr,n));
sc.close();
}
}
If you have any doubt feel free to comment down below.
Comments
Post a Comment
if you have any doubts let me know.