Program to find pairs in array that XOR to a given value

Question

I am given an array and a value x.

Input example:

2 3
1 2

Where n (length of array) = 2, the value x = 3, and the next line (1, 2) contains the values in the array. I have to find the pairs of indices i, j so that a[i] XOR a[j] = x.

What I have implemented:

import java.util.HashSet;
import java.util.Scanner;

public class Main {

  public static void main(String[] args) {
   Scanner sc = new Scanner(System.in);

   int n = sc.nextInt();
   int x = sc.nextInt();

   int[] arr = new int[n];

   HashSet<Integer> hash = new HashSet<Integer>();

   for (int i = 0; i < n; i++) {
     arr[i] = sc.nextInt();
     hash.add(arr[i]);
   }

   int count = 0;

   for (int i = 0; i < n; i++) {
     if (hash.contains(arr[i]^x)) {
       count++;
     }
   }

   System.out.println(count/2);
  }

}

I have the divided the result by two because we only want to count a given pair once (only count [1, 2] not [1, 2] and [2, 1]).

I pass the given test above where the output is 1, and this supplementary one where the output is 2.

6 1
5 1 2 3 4 1

However I seem to fail some extra ones which I cannot see.

Answer 1

The problem is that you check "contains", but for duplicate values this only returns a single occurrence. By using a set you throw duplicates away. Instead you should have a HashMap with number of occurrences:

Map<Integer, Integer> hash = new HashMap<>();

for (int i = 0; i < n; i++) {
    arr[i] = sc.nextInt();
    if (!hash.containsKey(arr[i])) {
        hash.put(arr[i], 0)
    }
    hash.put(arr[i], hash.get(arr[i]) + 1);
}

int count = 0;

for (int i = 0; i < n; i++) {
    if (hash.containsKey(arr[i]^x)) {
        count += hash.get(arr[i]^x);
    }
}