Hackerrank-Cipher

baahu   November 12, 2016   No Comments on Hackerrank-Cipher

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 :

example1

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

example2

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
example3

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

Leave a Reply

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