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 so :

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

**Approach to solve the problem**

The solution to this problem can be derived using XOR operation

Lets take below as the input.

6 2

1110001

Which means that the un-encrypyted string length is 6 and it is written down 2 times, shifted by bits 0,1 bits as seen in the below image

ED – Encrypted Data

UD – UnEncrypted Data

1 .As evident from the above figure, the first bit of ED and UD is always the same

So UD= 1 _ _ _ _ _

2. We are aware that the XOR between 1st bit of UD and 2nd Bit of UD resulted in 2nd bit of ED, so with the behaviour of XOR operation we can come to a conclusion that 1st bit of UD(i.e1) XOR 2nd bit of ED(i.e 1) would give the 2nd bit of UD i.e 1 XOR 1 = 0

So UD= 1 0 _ _ _ _

3. We can get 3rd bit of UD by ==> (2nd bit of UD) XOR (3rd bit of ED)

So UD= 1 0 1 _ _ _

So on so forth….

By repeating this , we can determine that the UD is 101111

Below is the scala code for the same:

object Cipher { def main(args:Array[String]):Unit= { val sc = new java.util.Scanner (System.in); var line = sc.nextLine() var N = line.split(" ")(0).toInt var K = line.split(" ")(1).toInt var encryptedData:Array[Char] = sc.nextLine().toCharArray() //Since the data was read as a string, we need to subtract ascii value of 0 to get to the binary data. for(i<-0 to encryptedData.length-1) encryptedData(i) = (encryptedData(i).-('0')).toChar var unencryptedData:Array[Char] = new Array[Char](N); //First bit of unencrypted data is same as first bit of encrypted data unencryptedData(0) = encryptedData(0) for(i<-1 to unencryptedData.length-1) { var xorvalue= '\0' //Get the XOR of the K-1 bits for(j<- 1 to K-1) { if(i-j>=0) { xorvalue = (xorvalue^unencryptedData(i-j)).toChar } } //Now XOR with the ith encrypted to get the ith unecrypted bit unencryptedData(i) = (xorvalue ^ encryptedData(i)).toChar } //To print convert to get the character 0s and 1s by adding ascii value of '0' for(i<-0 to unencryptedData.length-1) print((unencryptedData(i)+'0').toChar) } }