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.