Java XOR operation

Question

I came across this problem wherein all of the program was given barring only a piece of logic. What could be filled in the following problem's missing lines?

Problem Statement

Jack and Daniel are friends. They want to encrypt their conversation so that they can save themselves from interception by a detective agency. So they invent a new cipher. Every message is encoded to its binary representation B of length N. Then it is written down K times, shifted by 0,1,...,K−1 bits. If B=1001010 and K=4 it looks like:

Then calculate XOR in every column and write it down. This number is called S. For example, XOR-ing the numbers in the above example results in

1110100110

Then the encoded message S and K are sent to Daniel.

Jack is using this encoding algorithm and asks Daniel to implement a decoding algorithm. Can you help Daniel implement this?

Input Format

The first line contains two integers N and K.
The second line contains string S of length N+K−1 consisting of ones and zeros.

Output Format

Decoded message of length N, consisting of ones and zeros.

Constraints

1≤N≤10^6,
1≤K≤10^6
|S|=N+K−1
It is guaranteed that S is correct.

Sample Input#00

   7 4
   1110100110

Sample Output#00

Sample Input#01

   6 2
   1110001

Sample Output#01

Explanation for Input#00

Explainatin for Input#01

101111
 101111
-------
1110001

import java.io.*;

public class Solution {

    public static void solve(Input in, PrintWriter out) throws IOException {
        int n = in.nextInt();
        int k = in.nextInt();
        char[] c = in.next().toCharArray();
        int x = 0;
        char[] ans = new char[n];
        for (int i = 0; i < n; ++i) {
            ans[i] = (char) (((c[i] - '0') ^ x) + '0');// I understand we are converting the character into integer (c[i] - '0') then xoring it with x which is holding 0 and then again adding '0' to convert back it into character.
            x ^= ans[i] - '0';// But why are we doing this!!. From this line onward things are not clear.
            if (i >= k - 1) {
                ****FILL THE MISSING LINE HERE****

            }
        }
        out.println(ans);
    }

    public static void main(String[] args) throws IOException {
        PrintWriter out = new PrintWriter(System.out);
        solve(new Input(new BufferedReader(new InputStreamReader(System.in))), out);
        out.close();
    }

    static class Input {
        BufferedReader in;
        StringBuilder sb = new StringBuilder();

        public Input(BufferedReader in) {
            this.in = in;
        }

        public Input(String s) {
            this.in = new BufferedReader(new StringReader(s));
        }

        public String next() throws IOException {
            sb.setLength(0);
            while (true) {
                int c = in.read();
                if (c == -1) {
                    return null;
                }
                if (" 

	".indexOf(c) == -1) {
                    sb.append((char)c);
                    break;
                }
            }
            while (true) {
                int c = in.read();
                if (c == -1 || " 

	".indexOf(c) != -1) {
                    break;
                }
                sb.append((char)c);
            }
            return sb.toString();
        }

        public int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        public long nextLong() throws IOException {
            return Long.parseLong(next());
        }

        public double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }
    }
}

willeM_ Van Onsem · Accepted Answer

Note: please read the explenation, simply solving challenges by copy-pasting the answer is not useful.

The constraint you can exploit is that

The first bit is untouched by the encryption algorithm.

Indeed because all "masks" are shifted at least one to the right. So you can assume that the first bit of the encrypted part is the first bit of the decrypted content as well.

Now that you know the first bit, you can easily reconstruct the second bit, since it is only xor-ed with the first one we already know. So know we can calculate the second.

The third bit is xor-ed with the first and the second, so what one basically does is maintain a value that is the xor of all already obtained values and xor this with the next value. Intially the value is zero.

Example:

Take the first sample input:

1110100110

We can derive the first bit is a 1. So now we know that the mask for the second bit is of the form:

       1110100110
mask    1????????
result 10

Now we know that the mask for the third bit is the xor of 1 and 0 thus 1.

       1110100110
mask    11???????
result 100

iteratively this will eventually result in:

index      0123456789       
data       1110100110
submasks    1001010
             1001010
              1001010
mask       0111??????
result     1001??????

Now after k-1 iterations, one no longer has an additional submask, indeed: one only writes k times the data one for the result, and k-1 times the submask. So now we don't xor over new data anymore: we only xor the last k bits of the result, this can be done by unxoring (or simply xoring) of the bit of the result k positions to the left.

For the next mask, we thus xor our state (last bit of the mask) with both the last bit of the result (1) and the first bit of the result (1) which means the state remains the same (1):

index      0123456789
data       1110100110
submasks    1001010
             1001010
              1001010
mask       01111?????
result     10010?????

Now we xor with the last result bit (0) and the second result bit (0):

index      0123456789
data       1110100110
submasks    1001010
             1001010
              1001010
mask       011111????
result     100101????

For the next, we xor with the last (1) and the third (0) thus we swap the state. By keep doing this process, we eventually end with:

index      0123456789
data       1110100110
submasks    1001010
             1001010
              1001010
mask       0111110???
result     1001010???

Now we are no longer interested in the remaining bits so we terminate.

What must be modified?

In the if-part, we need to xor (^) with the i-(k-1)-th bit as well:

if (i >= k - 1) {
    x ^= ans[i-(k-1)] - '0';
}