Question

Write pseudocode for an algorithm that calculates the Hamming distance between two strings s1 and s2 of the same length n. What is the complexity of your algorithm?

Answer 1

Algo-

function Find_Hamming_distance(string s1, string s2)

Declare 3 variable i,n,counter=0 where n will store length of string,counter varible will store number of position where character mismatch and i will udes as index.

run while loop till n>0, where n is length of string

starting from index 0,check if at same index in both sring,character are different, then increase counter =counter+1. Move index one position ahead after each iteration.

After the end of while loop, return counter.

Pseudocode-

Find_Hamming_distance(string s1, string s2)

{

      counter=0 //store hamming distance

      n=length of any string

      while(n--)

      {

       if(s1[i]!=s2[i])

       {

        counter=counter+1

        }

       i=i+1

     }

return counter;

}

Complexity of algorithm is O(n) where n is length of string.

Complete code in c++

#include<bits/stdc++.h>
using namespace std;

int Find_Hamming_distance(string s1,string s2)
{
int i = 0, counter=0; //counter will store hamming distance
int n=s1.length();
while (n--)
{
if (s1[i] != s2[i]) //check if character are not same then increment counter variable by 1
counter++;
i++;
}
return counter;
}

int main()
{
string s1 = "checkprice";
string s2 = "shackprise";

cout << Find_Hamming_distance (s1, s2);

return 0;
}

output