Codechef: KMXOR Solution

by | May 22, 2018

Codechef: KMXOR Solution

by | May 22, 2018

PROBLEM

Find an array A of size N such that 1<=A[i]<=K and the XOR of all the elements is maximum.

The complete text of the problem can be found on Codechef.

OBSERVATION 

The i-th bit of XOR-result will be:

  • 1 if no. of 1s encountered is odd
  • 0 if no. of 1s encountered is even

In order to get the maximum XOR-result, for every bit, we should have encountered an odd number of 1s.

SOLUTION

Let A[0] = K.

Assuming N>1, let A[1] be the number whose binary number is such that for all the bits that lie on the right of MSB of K, only those bits are set that are not set in K.

For example,

If        K      = 20 ( 10100 ),

Then A[0]  = 20 ( 10100 ),

         A[1]   = 11 ( 01011 )

We have the XOR-result we need. However, we need to fill the rest of the elements. Fill them with 1 ( 0001 ).

Now, count the number 1s that have been encountered on LSB in the array.

If the count is odd, leave the array as it is.

Else

         If       A[0] has the LSB set, unset it. We cannot do the vice-versa as it will make A[0] greater than K.

          Else Toggle the LSB in A[1] provided, it lies between 1 and K (inclusive).

That’s it, you have the required array. This is because, for the rest of the bits, we are sure that the number of 1s encountered will be odd.

JAVA IMPLEMENTATION

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
import java.io.*;
import java.util.*;
class KMXOR
{
    public static void main(String args[])throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder out = new StringBuilder("");
       
        int t, n, k,
            lsbCount, msb, tmp;
        int[] a;
 
        t = Integer.parseInt(br.readLine());
        while(t-->0) {
            st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            k = Integer.parseInt(st.nextToken());
            a = new int[n];
            lsbCount = 0;

            if(n==1) {
                out = out.append(k+"\\n");
                continue;
            }
 
            a[0] = k;
            if( isBitSet(a[0], 0) ) lsbCount++;

           
            msb = (int)( Math.log(a[0])/Math.log(2) );  //position of MSB (0 means LSB)            
            for(int i=msb-1;i>=0;i--)
            {
                if(!isBitSet(a[0], i))
                    a[1] = a[1] | (1<<i);
            }
           
            //Corner case
            if(a[1]==0) a[1] = 1;        
            if( isBitSet(a[1], 0) ) lsbCount++;

            //Fill remaining elements with 1
            for(int i=2;i<n;i++)
                a[i] = 1;
            lsbCount += n-2;
 
            if( lsbCount%2 == 0 )
            {
                if(isBitSet(a[0], 0)) {
                    tmp = (a[0]/2) * 2;
                    if(tmp>0) a[0] = tmp;   //if a[0] was 1, we cannot do this operation
                }
               
                else
                    if(isBitSet(a[1], 0)) {
                        tmp = (a[1]/2)*2;
                        if(tmp>0 && tmp<=k) a[1] = tmp;
                    }
                    else {
                        tmp = a[1] | 1;
                        if(tmp>0 && tmp<=k) a[1] = tmp;
                    }
                   
               
            }
 
            for(int i : a)
                out = out.append(i+" ");
            out = out.append("\\n");
        }
        System.out.print(out);
    }
 
    static boolean isBitSet(int n, int i) {
        return ( n & (1<<i) ) != 0;
    }
}

0 Comments

Submit a Comment

Your email address will not be published. Required fields are marked *

More from this Category