Decode the message from Data packets sent over the network
Over the network, messages are sent as data packets. Each data packet is a series of bytes (8bits = 1 byte). The task is to decode the data packet (str) of length N. The format of the data packet is as follows:
- The packet can be broken into 2 parts.
- The first byte represents a unique value, say K.
- The remaining bytes in the data packet represent the message to be decoded.
- Each message byte is to be XORed to the first byte, which results in a set of alphanumeric ASCII characters to get the readable message.
If the length of the data packet is not valid return -1.
Examples:
Input: str = β101010101110001011001111110001101100011011000101β, N = 48
Output: Hello
Explanation: Here K = 10101010, and the other bytes are:
β11100010β, β11001111β, β11000110β, β11000110β, β11000101β.
The Xor value with K are β01001000β, β01100101β, β01101100β, β01101100β, β01101111β
which have ASCII values 72, 101, 108, 108, 111 and the characters are βHβ, βeβ, βlβ, βlβ and βoβ.Input: str = β1010101011100010111000101111β, N = 28
Output: -1
Explanation: The length of the packet is not valid. One byte of the message is missing some bits.
Approach: the solution to the problem is based on implementation. Check for the validity of the packet length. If valid, then do as said in the question. Follow the steps mentioned below:
- Check if the input length is divisible by 8, if not, return -1.
- Now, for the first byte i.e first 8 bits, calculate the decimal value and store it in a variable.
- Now, for every coming byte, XOR it with the first byte stored and print the corresponding character which has the ASCII value.
Below is the implementation of the above approach.
C++
// C++ program to implement the approach #include <bits/stdc++.h> using namespace std; // Function to decode the message string decode(string str, int N) { // If length of packet is invalid if (N % 8 != 0) return "-1" ; string res = "" ; int j = 0, k = 0, first = 0, K = 0; for ( int i = 0; i < N; i++) { k++; // If one byte length is reached if (k == 8) { k = 0; string s = str.substr(j, i + 1 -j); bitset<32> b(s); int n = ( int )(b.to_ulong()); j = i + 1; // If not the first byte add // character to decoded message if (first == 1) { int z = n ^ K; char ch = ( char )z; res += ch; } // If it is the first byte else if (first == 0) { first = 1; K = n; } } } return res; } // Driver code int main() { string str = "101010101110001011001111110001101100011011000101" ; int N = 48; string ans = decode(str, N); cout<<ans; } // This code is contributed by Pushpesh Raj. |
Java
// Java program to implement the approach import java.util.*; public class Main { // Function to decode the message static String decode(String str, int N) { // If length of packet is invalid if (N % 8 != 0 ) return "-1" ; String res = "" ; int j = 0 , k = 0 , first = 0 , K = 0 ; for ( int i = 0 ; i < N; i++) { k++; // If one byte length is reached if (k == 8 ) { k = 0 ; String s = str.substring(j, i + 1 ); int n = Integer.parseInt(s, 2 ); j = i + 1 ; // If not the first byte add // character to decoded message if (first == 1 ) { int z = n ^ K; char ch = ( char )z; res += ch; } // If it is the first byte else if (first == 0 ) { first = 1 ; K = n; } } } return res; } // Driver code public static void main(String[] args) { String str = "101010101110001011001111110001101100011011000101" ; int N = 48 ; String ans = decode(str, N); System.out.println(ans); } } |
Python3
# Python code for the above approach # Function to decode the message def decode(strr: str , N: int ) - > str : # If length of packet is invalid if N % 8 ! = 0 : return "-1" res = "" j, k, first, K = 0 , 0 , 0 , 0 for i in range (N): k + = 1 # If one byte length is reached if k = = 8 : k = 0 s = strr[j : i + 1 ] n = int (s, 2 ) j = i + 1 # If not the first byte add # character to decoded message if first = = 1 : z = n ^ K ch = chr (z) res + = ch # If it is the first byte elif first = = 0 : first = 1 K = n return res # Driver code if __name__ = = "__main__" : strr = "101010101110001011001111110001101100011011000101" N = 48 ans = decode(strr, N) print (ans) # This code is contributed by N SaiSuprabhanu |
C#
// C# program to implement the approach using System; using System.Data; public class GFG { // Function to decode the message static String decode(String str, int N) { // If length of packet is invalid if (N % 8 != 0) return "-1" ; String res = "" ; int j = 0, k = 0, first = 0, K = 0; for ( int i = 0; i < N; i++) { k++; // If one byte length is reached if (k == 8) { k = 0; String s = str.Substring(j, i + 1-j); int n = Convert.ToInt32(s,2); j = i + 1; // If not the first byte add // character to decoded message if (first == 1) { int z = n ^ K; char ch = ( char )z; res += ch; } // If it is the first byte else if (first == 0) { first = 1; K = n; } } } return res; } // Driver code public static void Main(String[] args) { String str = "101010101110001011001111110001101100011011000101" ; int N = 48; String ans = decode(str, N); Console.WriteLine(ans); } } // This code contributed by shikhasingrajput |
Javascript
<script> // JavaScript code for the above approach // Function to decode the message function decode(str, N) { // If length of packet is invalid if (N % 8 != 0) return "-1" ; let res = "" ; let j = 0, k = 0, first = 0, K = 0; for (let i = 0; i < N; i++) { k++; // If one byte length is reached if (k == 8) { k = 0; let s = str.slice(j, i + 1); let n = parseInt(s, 2); j = i + 1; // If not the first byte add // character to decoded message if (first == 1) { let z = n ^ K; let ch = String.fromCharCode(z); res += ch; } // If it is the first byte else if (first == 0) { first = 1; K = n; } } } return res; } // Driver code let str = "101010101110001011001111110001101100011011000101" ; let N = 48; let ans = decode(str, N); document.write(ans); // This code is contributed by Potta Lokesh </script> |
Hello
Time Complexity: O(N)
Auxiliary Space: O(logN)
Contact Us