CODEWITHSUNDEEP
javaarraysalgorithmxor
pavlos163
pavlos163

Reputation: 2890

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

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.

Upvotes: 0

Views: 604

Answers (3)

fafl
fafl

Reputation: 7385

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);
    }
}

Upvotes: 2

User_Targaryen
User_Targaryen

Reputation: 4225

Your logic of dividing the count by 2 as the final answer, is not correct. Replace your logic by the following:

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

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

   int count = 0;

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

   System.out.println(count);

Upvotes: 1

John Kugelman
John Kugelman

Reputation: 361917

Your program doesn't handle duplicate numbers properly. It deals with 5 1 2 3 4 1 okay because 1 isn't part of the solution. What if it is?

Let's say number a[i] ^ a[j] is a solution as is a[i] ^ a[k]. In other words, a[j] == a[k]. The line hash.contains(arr[i]^x) will only count a[i] once.

You can solve this by having nested for loops.

for (int i = ...) {
  for (int j = ...) {
    if (a[i] ^ a[j] == x) {
      count++;
    }
  }
}

This approach lets you get rid of the hash set. And if you're clever enough filling out the ... parts you can avoid double counting the pairs and won't have to divide count by 2.

Upvotes: 0

Related Questions