Maximizing XOR Hacker Rank

 Problem Link:

https://www.hackerrank.com/challenges/maximizing-xor/problem

Solution:

class Result {

    /*

     * Complete the 'maximizingXor' function below.

     *

     * The function is expected to return an INTEGER.

     * The function accepts the following parameters:

     *  1. INTEGER l

     *  2. INTEGER r

     */

    public static int maximizingXor(int l, int r) {

        PriorityQueue<Integer>pq=new PriorityQueue<Integer>(Collections.reverseOrder());

        

        for(int i=l;i<r;i++){

            for(int j=l+1;j<=r;j++){

                pq.add(i^j);

            }

        }

        return pq.peek();

    }

}

TIME COMPLEXITY:O(N^2)[N=r-l]

SPACE COMPLEXITY:O(1)

AUXILLARY SPACE:O(N)[Using Priority Queue of N size]

APPROACH:

Here we will traverse the whole array and simultaneously store values in the priority queue.

Later we remove the peek value of pq.

Peek value of queue will be maximum because in declaration we have said that

pq queue will be implemented in reverse order, which means highest will be at peak

and lowest at the bottom.

----------------------------------------------------------------------------------

Approach 2:

PriorityQueue<Integer>pq=new PriorityQueue<Integer>(Collections.reverseOrder());

        

        pq.add(0);

        for(int i=l;i<r;i++){

            for(int j=l+1;j<=r;j++){

                if(pq.peek()<(i^j)){

                    pq.remove();

                    pq.add(i^j);

                }

            }

        }

        return pq.peek();

TIME COMPLEXITY:O(N^2)[N=r-l]

SPACE COMPLEXITY:O(1)

AUXILLARY SPACE:O(1)[Using Priority Queue of 1 size]

APPROACH:

Here we will traverse the whole array and simultaneously we see whether the value inside

the queue is less than the incoming xor value. If yes we remove that value and add the

new greater value.

It is similar to the usage of another constant as int max and comparing it with value

every time while traversing.

------------------------------------------------------------------------------------

"Thanks For Reading.😇"

"Share Further To Increase Knowledge Treasure.😊"