Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

Cipher challenge

Sharing is caring!

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,\dots, K-1 bits.
If B=1001010 and K=4 it looks so:

1001010   
 1001010  
  1001010 
   1001010

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 \le N \le N^{6}
1 \le K \le N^{6}
|S| = N + K - 1
It is guaranteed that S is correct.

Sample Input#00

7 4
1110100110

Sample Output#00

1001010

Sample Input#01

6 2
1110001

Sample Output#01

101111

Explanation
Input#00

1001010
 1001010
  1001010
   1001010
----------
1110100110

Input#01

101111
 101111
-------
1110001

Solution

public class Cipher {
    public static void main(String[] args) throws FileNotFoundException {
        System.setIn(new FileInputStream(System.getProperty("user.home") + "/" + "in.txt"));
        Scanner in = new Scanner(System.in);

        int n = in.nextInt();
        int k = in.nextInt();
        char[] c = in.next().toCharArray();

        int[] ans = new int[n];

        ans[0] = c[0] == '1' ? 1 : 0;
        int tmp = ans[0];
        for (int i = 1; i < n; i++) {
            if (i < k) {
                if (i >= 2) {
                    tmp ^= ans[i - 1];
                }
            } else if (i >= k && i <= c.length - k) {
                tmp ^= ans[(i - k)]; // Remove left-most element
                tmp ^= ans[i - 1]; // Take new element
            } else {
                tmp ^= ans[(i - k)]; // Remove left-most element
            }

            if (c[i] == '0') {
                ans[i] = tmp;
            } else {
                ans[i] = tmp == 1 ? 0 : 1;
            }
        }

        for (int i : ans) {
            System.out.print(i);
        }
    }
}