Google OA Problem Based On Hashing







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