# Cipher challenge

**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 of length . Then it is written down times, shifted by bits.

If and it looks so:

1 2 3 4 |
1001010 1001010 1001010 1001010 |

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

1 |
1110100110 |

Then the encoded message and 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 and .

The second line contains string of length consisting of ones and zeros.

**Output Format**

Decoded message of length , consisting of ones and zeros.

**Constraints**

It is guaranteed that is correct.

**Sample Input#00**

1 2 |
7 4 1110100110 |

**Sample Output#00**

1 |
1001010 |

**Sample Input#01**

1 2 |
6 2 1110001 |

**Sample Output#01**

1 |
101111 |

**Explanation**

*Input#00*

1 2 3 4 5 6 |
1001010 1001010 1001010 1001010 ---------- 1110100110 |

*Input#01*

1 2 3 4 |
101111 101111 ------- 1110001 |

**Solution**

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 |
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); } } } |