Question

With being given two n-bit binary strings, verify if the strings are identical or not. Design a procedure showing all steps and write a pseudo-code. What is the complexity of the procedure? If it can tolerate some error, is there a better than linear time solution? If so, write the pseudo-code.

Answer 1

Solution: For both the binary strings to be identical, it means that the elements must be the same in both the strings at the corresponding positions in both the strings. It can be easily checked using a for or while loop and trying to match each and every element head-to-head from two arrays. Since it is just a single loop hence the problem would be solved in linear time and it would be O(n) where n is the size of both the strings. Given below, the pseudocode for the same:

1. Take two n-bit binary strings A[n] and B[n] as input.
2. Initialize a count variable C with 0.
3. Repeat steps 4 to 5.
4. Check A[iteration] = B[iteration], which is nothing but checking the elements from the both the arrays are same are not in a given iteration.
5. If they are same then increment the count variable C by 1, that is C = C + 1.
6. Check if value of C is equal to n.
   1. If yes, then the both the strings are identical.
   2. Else the strings are not identical.

Here's the solution to your question and it is absolutely correct, please please please provide it a 100% rating. Thanks for asking and happy learning!!