XOR GAME GEEKS FOR GEEKS

 Problem Link:

https://practice.geeksforgeeks.org/problems/xor-game2143/1#

(It is also the problem of the day for 10 February)

Solution:

class Solution{

    static int xorCal(int k){

      

        if(k!=1){

            String s=Integer.toBinaryString(k);

            //System.out.println(s);

            boolean flag=true;

            

           for(int i=0;i<s.length()-1;i++){

               if(s.charAt(i)!=s.charAt(i+1)){

                   flag=false;

                   break;

               }

           }

           if(flag){

              StringBuilder sb=new StringBuilder();

              sb.append(s);

              sb.deleteCharAt(0);

              int val=Integer.parseInt(sb.toString(),2);

              return val;

           }

           else{

               return -1;

           }

        }

        else{

            return 2;

        }

    }

}

TIME COMPLEXITY:[O(String Length) in the worst case all are 1 and in question given it will be for 63.][GFG Time:01./2.0]

SPACE COMPLEXITY: O(1)

AUXILLARY SPACE: O(1)

TOTAL TEST CASES:154

APPROACH USED:

Here we know the concept of XOR. 

For XOR: if we want 1 then (1,0) or (0,1) combination should be there.

and if we want 0 then (1,1) or (0,0) combination should be there.

Moreover, if we see the smallest number will exist for those which have continuous 1.

ex for 7 binary representation continuous 1 is there while for 6,110 binary has one zero.

We can also say that binary representation of number should not have 0, if 0 is found then the answer will be -1.

Now if we get a number that does not have 0 then how we will find the smallest number for that such it satisfies condition n^n+1 is equivalent to k ie the number.

For that, we will do one thing.

After checking that the binary representation of the number doesn't have 0 we will modify its binary representation as 

we will remove the MSB from binary representation and return the decimal number so formed.

eq for 63 binary is 111111 and number will be 31 and 32 such that 31^32=63

Hence if we remove MSB from 63 we get 31. as 111111=63 and 11111=31 while 100000 =32 and 

100000 ^ 011111=31.

Specifically, there is one case of 1 where we need to return 2 as output.

"Thanks For Reading.😇"

"Share Further To Increase Knowledge Treasure.😊"