Count Zeros XOR pairs Geeks For Geeks

 Problem Link:

https://practice.geeksforgeeks.org/problems/counts-zeros-xor-pairs0349/1

(It is also the problem of the day for 30 March 2022)

Solution:

class Complete{

    

   

    // Function for finding maximum and value pair

    public static long calculate (int arr[], int n) {

        HashMap<Integer,Integer>map=new HashMap<Integer,Integer>();

        for(int i=0;i<n;i++){

            if(map.containsKey(arr[i])){

                map.put(arr[i],map.get(arr[i])+1);

            }

            else{

                map.put(arr[i],1);

            }

        }

        long count=0;

        for(int a:map.keySet()){

            if(map.get(a)>1){

                count=count+(map.get(a)*(map.get(a)-1))/2;

            }

        }

        return count;

    }

    

    

}

Time Complexity: O(N)[GFG Time:0.2/7.3]

Space Complexity: O(N)[Array is given]

Auxiliary Space: O(N)[Map is used]

Approach Used:

Here we will store the frequency of every element on the map.

It is so because we know that xor of two same elements is 0. So first we will count the number of times an element is repeated and for that, we will use the map and store the element and frequency.

Now for finding pairs we know that pair is formed by two elements so taking that in mind we will use combinations of choosing 2 elements from the frequency of a specific element.

eg if the array is 2 3 3 3 10 2 3

then map is 

2 2 

3 4

10 1 

Here for xor, both elements should be the same ie elements should have a minimum of 2 frequencies.

so clearly 10 won't take part in xor pair.

Now frequency of 2 is 2 so number of pairs formed is 1 (ie nC2 => 2C2 => 1)

Similarly for 3 frequency is 4 so number of pairs formed are 6 (nC2= > 4C2 => 6)

In this way, total pairs can be 1+6 ie 7

Here we will be using a map so the time complexity will be O(N) and we are not storing so it won't be O(nlogn). However, in question, they asked for O(1) space and O(N log N) time but we are doing it in O(n) space and O(N) time.

"Thanks For Reading."

"Share Further To Increase Knowledge Treasure."