Question

. As input you are given two arrays: an array of numbers ? and an array ? of queries where each query is a target number. The array ? is unsorted and may contain duplicates. Your goal is, for each query ? in the array ?, count the number of pairs in the array ? that sums up to ?; that is, the number of distinct pairs of indices [?, ?], with ? < ?, such that ?[?] + ?[?] = ?. Write a method, twoSumQuery, that given an array of numbers ? and an array ? of queries, returns an array ? with the same length as ?, such that for every index ?, ?[?] is the answer to query ?[?]. Let ? denote the length of ? and ? the length of ?. Suppose that in the actual input for this problem, we have the condition that ? > ? . For example, ? = 1000 and ? = 10,000,000. Your method must have time complexity ?(?).

The following is a few sample runs:

Input :     ? = [0, 1, 2, 3, 4],   ? = [1, 3, 6, 10]

Return:   [1, 2, 1, 0]

Explanation: One pair in ? sums up to 1, namely (0, 1). Two pairs in ? sum up to 3, namely (0, 3) and (1, 2). One pair in ? sum up to 6, namely (2, 4). No pair in ? sums up to 10.

public class TwoSumQuery {
   public static int[] twoSumQuery(int[] A, int[] Q) {
      
       //Replace this line with your return statement
       return null;
   }

}

Answer 1

import java.util.Arrays;
import java.util.HashMap;

public class TwoSumQuery {
        
   public static int[] twoSumQuery(int[] A, int[] Q) {
           
           // We will first create a Hashmap which contains all the possible
           // sums which can be created from the array
           // as A[i] + A[j] with i < j
           HashMap<Integer, Integer> sumCount = new HashMap<>();
           
           for(int i=0; i<A.length; i++) {
                   for(int j=i+1; j<A.length; j++) {
                           int sum = A[i] + A[j];
                           sumCount.put(sum, 1 + sumCount.getOrDefault(sum, 0));
                   }
           }
           
           int result[] = new int[Q.length];
           
           for(int i=0; i<Q.length; i++) {
                   result[i] = sumCount.getOrDefault(Q[i], 0);
           }
           
           // The complexity is O(m), Since n is very less and hence time
           // to build the hashmap is very negligible.
           // As we iterate on array Q one by one, Hence it is O(m) complexity.
           
       return result;
   }
   
   public static void main(String args[]) {
           int A[] = {0, 1, 2, 3, 4};
           int Q[] = {1, 3, 6, 10};
           
           System.out.println(Arrays.toString(twoSumQuery(A, Q)));
   }

}

**************************************************

Thanks for your question. We try our best to help you with detailed answers, But in any case, if you need any modification or have a query/issue with respect to above answer, Please ask that in the comment section. We will surely try to address your query ASAP and resolve the issue.

Please consider providing a thumbs up to this question if it helps you. by Doing that, You will help other students, who are facing similar issue.