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 approachimport 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 messagedef 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 codeif __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 approachusing 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> |
Output
Hello
Time Complexity: O(N)
Auxiliary Space: O(logN)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
