Chapter 46: Equation Solving

Section 46.1: Linear Equation

There are two classes of methods for solving Linear Equations:

1. Direct Methods: Common characteristics of direct methods are that they transform the original equation
into equivalent equations that can be solved more easily, means we get solve directly from an equation.

2. Iterative Method: Iterative or Indirect Methods, start with a guess of the solution and then repeatedly refine
the solution until a certain convergence criterion is reached. Iterative methods are generally less efficient
than direct methods because large number of operations required. Example- Jacobi's Iteration Method,
Gauss-Seidal Iteration Method.

Implementation in C-

//Implementation of Jacobi's Method

void JacobisMethod(int n, double x[n], double b[n], double a[n][n]){
double Nx[n]; //modified form of variables
int rootFound=0; //flag

int i, j;
while(!rootFound){
for(i=0; i<n; i++){ //calculation
Nx[i]=b[i];

for(j=0; j<n; j++){

if(i!=j) Nx[i] = Nx[i]-a[i][j]*x[j];
}
Nx[i] = Nx[i] / a[i][i];
}

rootFound=1; //verification
for(i=0; i<n; i++){
if(!( (Nx[i]-x[i])/x[i] > -0.000001 && (Nx[i]-x[i])/x[i] < 0.000001 )){
rootFound=0;
break;
}
}

for(i=0; i<n; i++){ //evaluation

x[i]=Nx[i];
}
}

return ;
}

//Implementation of Gauss-Seidal Method

void GaussSeidalMethod(int n, double x[n], double b[n], double a[n][n]){
double Nx[n]; //modified form of variables
int rootFound=0; //flag

int i, j;
for(i=0; i<n; i++){ //initialization
Nx[i]=x[i];
}

[Link] – Algorithms Notes for Professionals 214

 while(!rootFound){
for(i=0; i<n; i++){ //calculation
Nx[i]=b[i];

for(j=0; j<n; j++){

if(i!=j) Nx[i] = Nx[i]-a[i][j]*Nx[j];
}
Nx[i] = Nx[i] / a[i][i];
}

rootFound=1; //verification
for(i=0; i<n; i++){
if(!( (Nx[i]-x[i])/x[i] > -0.000001 && (Nx[i]-x[i])/x[i] < 0.000001 )){
rootFound=0;
break;
}
}

for(i=0; i<n; i++){ //evaluation

x[i]=Nx[i];
}
}

return ;
}

//Print array with comma separation

void print(int n, double x[n]){
int i;
for(i=0; i<n; i++){
printf("%lf, ", x[i]);
}
printf("\n\n");

return ;
}

int main(){
//equation initialization
int n=3; //number of variables

double x[n]; //variables

double b[n], //constants

a[n][n]; //arguments

//assign values
a[0][0]=8; a[0][1]=2; a[0][2]=-2; b[0]=8; //8x₁+2x₂-2x₃+8=0
a[1][0]=1; a[1][1]=-8; a[1][2]=3; b[1]=-4; //x₁-8x₂+3x₃-4=0
a[2][0]=2; a[2][1]=1; a[2][2]=9; b[2]=12; //2x₁+x₂+9x₃+12=0

int i;

for(i=0; i<n; i++){ //initialization

x[i]=0;
}
JacobisMethod(n, x, b, a);
print(n, x);

for(i=0; i<n; i++){ //initialization

[Link] – Algorithms Notes for Professionals 215

 x[i]=0;
}
GaussSeidalMethod(n, x, b, a);
print(n, x);

return 0;
}

Section 46.2: Non-Linear Equation

An equation of the type f(x)=0 is either algebraic or transcendental. These types of equations can be solved by
using two types of methods-

1. Direct Method: This method gives the exact value of all the roots directly in a finite number of steps.

2. Indirect or Iterative Method: Iterative methods are best suited for computer programs to solve an
equation. It is based on the concept of successive approximation. In Iterative Method there are two ways to
solve an equation-

Bracketing Method: We take two initial points where the root lies in between them. Example-
Bisection Method, False Position Method.

Open End Method: We take one or two initial values where the root may be any-where. Example-
Newton-Raphson Method, Successive Approximation Method, Secant Method.

Implementation in C:

/// Here define different functions to work with

#define f(x) ( ((x)*(x)*(x)) - (x) - 2 )
#define f2(x) ( (3*(x)*(x)) - 1 )
#define g(x) ( cbrt( (x) + 2 ) )

/**
* Takes two initial values and shortens the distance by both side.
**/
double BisectionMethod(){
double root=0;

double a=1, b=2;

double c=0;

int loopCounter=0;
if(f(a)*f(b) < 0){
while(1){
loopCounter++;
c=(a+b)/2;

if(f(c)<0.00001 && f(c)>-0.00001){

root=c;
break;
}

if((f(a))*(f(c)) < 0){

b=c;
}else{
a=c;
}

[Link] – Algorithms Notes for Professionals 216

 }
}
printf("It took %d loops.\n", loopCounter);

return root;
}

/**
* Takes two initial values and shortens the distance by single side.
**/
double FalsePosition(){
double root=0;

double a=1, b=2;

double c=0;

int loopCounter=0;
if(f(a)*f(b) < 0){
while(1){
loopCounter++;

c=(a*f(b) - b*f(a)) / (f(b) - f(a));

/*/printf("%lf\t %lf \n", c, f(c));/**////test

if(f(c)<0.00001 && f(c)>-0.00001){
root=c;
break;
}

if((f(a))*(f(c)) < 0){

b=c;
}else{
a=c;
}
}
}
printf("It took %d loops.\n", loopCounter);

return root;
}

/**
* Uses one initial value and gradually takes that value near to the real one.
**/
double NewtonRaphson(){
double root=0;

double x1=1;
double x2=0;

int loopCounter=0;
while(1){
loopCounter++;

x2 = x1 - (f(x1)/f2(x1));
/*/printf("%lf \t %lf \n", x2, f(x2));/**////test

if(f(x2)<0.00001 && f(x2)>-0.00001){

root=x2;
break;
}

[Link] – Algorithms Notes for Professionals 217

 x1=x2;
}
printf("It took %d loops.\n", loopCounter);

return root;
}

/**
* Uses one initial value and gradually takes that value near to the real one.
**/
double FixedPoint(){
double root=0;
double x=1;

int loopCounter=0;
while(1){
loopCounter++;

if( (x-g(x)) <0.00001 && (x-g(x)) >-0.00001){

root = x;
break;
}

/*/printf("%lf \t %lf \n", g(x), x-(g(x)));/**////test

x=g(x);
}
printf("It took %d loops.\n", loopCounter);

return root;
}

/**
* uses two initial values & both value approaches to the root.
**/
double Secant(){
double root=0;

double x0=1;
double x1=2;
double x2=0;

int loopCounter=0;
while(1){
loopCounter++;

/*/printf("%lf \t %lf \t %lf \n", x0, x1, f(x1));/**////test

if(f(x1)<0.00001 && f(x1)>-0.00001){

root=x1;
break;
}

x2 = ((x0*f(x1))-(x1*f(x0))) / (f(x1)-f(x0));

x0=x1;
x1=x2;
}
printf("It took %d loops.\n", loopCounter);

return root;
}

[Link] – Algorithms Notes for Professionals 218

int main(){
double root;

root = BisectionMethod();
printf("Using Bisection Method the root is: %lf \n\n", root);

root = FalsePosition();
printf("Using False Position Method the root is: %lf \n\n", root);

root = NewtonRaphson();
printf("Using Newton-Raphson Method the root is: %lf \n\n", root);

root = FixedPoint();
printf("Using Fixed Point Method the root is: %lf \n\n", root);

root = Secant();
printf("Using Secant Method the root is: %lf \n\n", root);

return 0;
}

[Link] – Algorithms Notes for Professionals 219

Chapter 47: Longest Common
Subsequence
Section 47.1: Longest Common Subsequence Explanation
One of the most important implementations of Dynamic Programming is finding out the Longest Common
Subsequence. Let's define some of the basic terminologies first.

Subsequence:

A subsequence is a sequence that can be derived from another sequence by deleting some elements without
changing the order of the remaining elements. Let's say we have a string ABC. If we erase zero or one or more than
one character from this string we get the subsequence of this string. So the subsequences of string ABC will be
{"A", "B", "C", "AB", "AC", "BC", "ABC", " "}. Even if we remove all the characters, the empty string will also be a
subsequence. To find out the subsequence, for each characters in a string, we have two options - either we take the
character, or we don't. So if the length of the string is n, there are 2n subsequences of that string.

Longest Common Subsequence:

As the name suggest, of all the common subsequencesbetween two strings, the longest common subsequence(LCS)
is the one with the maximum length. For example: The common subsequences between "HELLOM" and "HMLD"
are "H", "HL", "HM" etc. Here "HLL" is the longest common subsequence which has length 3.

Brute-Force Method:

We can generate all the subsequences of two strings using backtracking. Then we can compare them to find out the
common subsequences. After we'll need to find out the one with the maximum length. We have already seen that,
there are 2n subsequences of a string of length n. It would take years to solve the problem if our n crosses 20-25.

Dynamic Programming Method:

Let's approach our method with an example. Assume that, we have two strings abcdaf and acbcf. Let's denote
these with s1 and s2. So the longest common subsequence of these two strings will be "abcf", which has length 4.
Again I remind you, subsequences need not be continuous in the string. To construct "abcf", we ignored "da" in s1
and "c" in s2. How do we find this out using Dynamic Programming?

We'll start with a table (a 2D array) having all the characters of s1 in a row and all the characters of s2 in column.
Here the table is 0-indexed and we put the characters from 1 to onwards. We'll traverse the table from left to right
for each row. Our table will look like:

0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+

[Link] – Algorithms Notes for Professionals 220

 5 | f | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+

Here each row and column represent the length of the longest common subsequence between two strings if we
take the characters of that row and column and add to the prefix before it. For example: Table[2][3] represents the
length of the longest common subsequence between "ac" and "abc".

The 0-th column represents the empty subsequence of s1. Similarly the 0-th row represents the empty
subsequence of s2. If we take an empty subsequence of a string and try to match it with another string, no matter
how long the length of the second substring is, the common subsequence will have 0 length. So we can fill-up the 0-
th rows and 0-th columns with 0's. We get:

0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+

Let's begin. When we're filling Table[1][1], we're asking ourselves, if we had a string a and another string a and
nothing else, what will be the longest common subsequence here? The length of the LCS here will be 1. Now let's
look at Table[1][2]. We have string ab and string a. The length of the LCS will be 1. As you can see, the rest of the
values will be also 1 for the first row as it considers only string a with abcd, abcda, abcdaf. So our table will look
like:

0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+

For row 2, which will now include c. For Table[2][1] we have ac on one side and a on the other side. So the length of
the LCS is 1. Where did we get this 1 from? From the top, which denotes the LCS a between two substrings. So what
we are saying is, if s1[2] and s2[1] are not same, then the length of the LCS will be the maximum of the length of

[Link] – Algorithms Notes for Professionals 221

LCS at the top, or at the left. Taking the length of the LCS at the top denotes that, we don't take the current
character from s2. Similarly, Taking the length of the LCS at the left denotes that, we don't take the current
character from s1 to create the LCS. We get:

0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | 0 | 1 | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+

So our first formula will be:

if s2[i] is not equal to s1[j]

Table[i][j] = max(Table[i-1][j], Table[i][j-1]
endif

Moving on, for Table[2][2] we have string ab and ac. Since c and b are not same, we put the maximum of the top or
left here. In this case, it's again 1. After that, for Table[2][3] we have string abc and ac. This time current values of
both row and column are same. Now the length of the LCS will be equal to the maximum length of LCS so far + 1.
How do we get the maximum length of LCS so far? We check the diagonal value, which represents the best match
between ab and a. From this state, for the current values, we added one more character to s1 and s2 which
happened to be the same. So the length of LCS will of course increase. We'll put 1 + 1 = 2 in Table[2][3]. We get,

0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | 0 | 1 | 1 | 2 | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+

So our second formula will be:

if s2[i] equals to s1[j]

Table[i][j] = Table[i-1][j-1] + 1
endif

[Link] – Algorithms Notes for Professionals 222

We have defined both the cases. Using these two formulas, we can populate the whole table. After filling up the
table, it will look like this:

0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | 0 | 1 | 1 | 2 | 2 | 2 | 2 |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | 0 | 1 | 2 | 2 | 2 | 2 | 2 |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | 0 | 1 | 2 | 3 | 3 | 3 | 3 |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | 0 | 1 | 2 | 3 | 3 | 3 | 4 |
+-----+-----+-----+-----+-----+-----+-----+-----+

The length of the LCS between s1 and s2 will be Table[5][6] = 4. Here, 5 and 6 are the length of s2 and s1
respectively. Our pseudo-code will be:

Procedure LCSlength(s1, s2):

Table[0][0] = 0
for i from 1 to [Link]
Table[0][i] = 0
endfor
for i from 1 to [Link]
Table[i][0] = 0
endfor
for i from 1 to [Link]
for j from 1 to [Link]
if s2[i] equals to s1[j]
Table[i][j] = Table[i-1][j-1] + 1
else
Table[i][j] = max(Table[i-1][j], Table[i][j-1])
endif
endfor
endfor
Return Table[[Link]][[Link]]

The time complexity for this algorithm is: O(mn) where m and n denotes the length of each strings.

How do we find out the longest common subsequence? We'll start from the bottom-right corner. We will check
from where the value is coming. If the value is coming from the diagonal, that is if Table[i-1][j-1] is equal to
Table[i][j] - 1, we push either s2[i] or s1[j] (both are the same) and move diagonally. If the value is coming from top,
that means, if Table[i-1][j] is equal to Table[i][j], we move to the top. If the value is coming from left, that means, if
Table[i][j-1] is equal to Table[i][j], we move to the left. When we reach the leftmost or topmost column, our search
ends. Then we pop the values from the stack and print them. The pseudo-code:

Procedure PrintLCS(LCSlength, s1, s2)

temp := LCSlength
S = stack()
i := [Link]
j := [Link]
while i is not equal to 0 and j is not equal to 0
if Table[i-1][j-1] == Table[i][j] - 1 and s1[j]==s2[i]

[Link] – Algorithms Notes for Professionals 223

 [Link](s1[j]) //or [Link](s2[i])
i := i - 1
j := j - 1
else if Table[i-1][j] == Table[i][j]
i := i-1
else
j := j-1
endif
endwhile
while S is not empty
print([Link])
endwhile

Point to be noted: if both Table[i-1][j] and Table[i][j-1] is equal to Table[i][j] and Table[i-1][j-1] is not equal to
Table[i][j] - 1, there can be two LCS for that moment. This pseudo-code doesn't consider this situation. You'll have
to solve this recursively to find multiple LCSs.

The time complexity for this algorithm is: O(max(m, n)).

[Link] – Algorithms Notes for Professionals 224

Chapter 48: Longest Increasing
Subsequence
Section 48.1: Longest Increasing Subsequence Basic
Information
The Longest Increasing Subsequence problem is to find subsequence from the give input sequence in which
subsequence's elements are sorted in lowest to highest order. All subsequence are not contiguous or unique.

Application of Longest Increasing Subsequence:

Algorithms like Longest Increasing Subsequence, Longest Common Subsequence are used in version control
systems like Git and etc.

Simple form of Algorithm:

1. Find unique lines which are common to both documents.

2. Take all such lines from the first document and order them according to their appearance in the second
document.
3. Compute the LIS of the resulting sequence (by doing a Patience Sort), getting the longest matching sequence
of lines, a correspondence between the lines of two documents.
4. Recurse the algorithm on each range of lines between already matched ones.

Now let us consider a simpler example of the LCS problem. Here, input is only one sequence of distinct integers
a1,a2,...,an., and we want to find the longest increasing subsequence in it. For example, if input is 7,3,8,4,2,6
then the longest increasing subsequence is 3,4,6.

The easiest approach is to sort input elements in increasing order, and apply the LCS algorithm to the original and
sorted sequences. However, if you look at the resulting array you would notice that many values are the same, and
the array looks very repetitive. This suggest that the LIS (longest increasing subsequence) problem can be done
with dynamic programming algorithm using only one-dimensional array.

Pseudo Code:

1. Describe an array of values we want to compute.

For 1 <= i <= n, let A(i) be the length of a longest increasing sequence of input. Note that the length we are
ultimately interested in is max{A(i)|1 ≤ i ≤ n}.
2. Give a recurrence.
For 1 <= i <= n, A(i) = 1 + max{A(j)|1 ≤ j < i and input(j) < input(i)}.
3. Compute the values of A.
4. Find the optimal solution.

The following program uses A to compute an optimal solution. The first part computes a value m such that A(m) is
the length of an optimal increasing subsequence of input. The second part computes an optimal increasing
subsequence, but for convenience we print it out in reverse order. This program runs in time O(n), so the entire
algorithm runs in time O(n^2).

Part 1:

m ← 1
for i : 2..n
if A(i) > A(m) then

[Link] – Algorithms Notes for Professionals 225

 m ← i
end if
end for

Part 2:

put a
while A(m) > 1 do
i ← m−1
while not(ai < am and A(i) = A(m)−1) do
i ← i−1
end while
m ← i
put a
end while

Recursive Solution:

Approach 1:

LIS(A[1..n]):
if (n = 0) then return 0
m = LIS(A[1..(n − 1)])
B is subsequence of A[1..(n − 1)] with only elements less than a[n]
(* let h be size of B, h ≤ n-1 *)
m = max(m, 1 + LIS(B[1..h]))
Output m

Time complexity in Approach 1 : O(n*2^n)

Approach 2:

LIS(A[1..n], x):
if (n = 0) then return 0
m = LIS(A[1..(n − 1)], x)
if (A[n] < x) then
m = max(m, 1 + LIS(A[1..(n − 1)], A[n]))
Output m

MAIN(A[1..n]):
return LIS(A[1..n], ∞)

Time Complexity in Approach 2: O(n^2)

Approach 3:

LIS(A[1..n]):
if (n = 0) return 0
m = 1
for i = 1 to n − 1 do
if (A[i] < A[n]) then
m = max(m, 1 + LIS(A[1..i]))
return m

MAIN(A[1..n]):
return LIS(A[1..i])

[Link] – Algorithms Notes for Professionals 226

Time Complexity in Approach 3: O(n^2)

Iterative Algorithm:

Computes the values iteratively in bottom up fashion.

LIS(A[1..n]):
Array L[1..n]
(* L[i] = value of LIS ending(A[1..i]) *)
for i = 1 to n do
L[i] = 1
for j = 1 to i − 1 do
if (A[j] < A[i]) do
L[i] = max(L[i], 1 + L[j])
return L

MAIN(A[1..n]):
L = LIS(A[1..n])
return the maximum value in L

Time complexity in Iterative approach: O(n^2)

Auxiliary Space: O(n)

Lets take {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15} as input. So, Longest Increasing Subsequence for the given
input is {0, 2, 6, 9, 11, 15}.

[Link] – Algorithms Notes for Professionals 227

Chapter 49: Check two strings are
anagrams
Two string with same set of character is called anagram. I have used javascript here.

We will create an hash of str1 and increase count +1. We will loop on 2nd string and check all characters are there
in hash and decrease value of hash key. Check all value of hash key are zero will be anagram.

Section 49.1: Sample input and output

Ex1:

let str1 = 'stackoverflow';

let str2 = 'flowerovstack';

These strings are anagrams.

// Create Hash from str1 and increase one count.

hashMap = {
s : 1,
t : 1,
a : 1,
c : 1,
k : 1,
o : 2,
v : 1,
e : 1,
r : 1,
f : 1,
l : 1,
w : 1
}

You can see hashKey 'o' is containing value 2 because o is 2 times in string.

Now loop over str2 and check for each character are present in hashMap, if yes, decrease value of hashMap Key,
else return false (which indicate it's not anagram).

hashMap = {
s : 0,
t : 0,
a : 0,
c : 0,
k : 0,
o : 0,
v : 0,
e : 0,
r : 0,
f : 0,
l : 0,
w : 0
}

Now, loop over hashMap object and check all values are zero in the key of hashMap.

[Link] – Algorithms Notes for Professionals 228

In our case all values are zero so its a anagram.

Section 49.2: Generic Code for Anagrams

(function(){

var hashMap = {};

function isAnagram (str1, str2) {

if([Link] !== [Link]){

return false;
}

// Create hash map of str1 character and increase value one (+1).
createStr1HashMap(str1);

// Check str2 character are key in hash map and decrease value by one(-1);
var valueExist = createStr2HashMap(str2);

// Check all value of hashMap keys are zero, so it will be anagram.

return isStringsAnagram(valueExist);
}

function createStr1HashMap (str1) {

[].[Link](str1, function(value, index, array){
hashMap[value] = value in hashMap ? (hashMap[value] + 1) : 1;
return value;
});
}

function createStr2HashMap (str2) {

var valueExist = [].[Link](str2, function(value, index, array){
if(value in hashMap) {
hashMap[value] = hashMap[value] - 1;
}
return value in hashMap;
});
return valueExist;
}

function isStringsAnagram (valueExist) {

if(!valueExist) {
return valueExist;
} else {
var isAnagram;
for(var i in hashMap) {
if(hashMap[i] !== 0) {
isAnagram = false;
break;
} else {
isAnagram = true;
}
}

return isAnagram;
}
}

isAnagram('stackoverflow', 'flowerovstack'); // true

isAnagram('stackoverflow', 'flowervvstack'); // false

[Link] – Algorithms Notes for Professionals 229

})();

Time complexity: 3n i.e O(n).

[Link] – Algorithms Notes for Professionals 230

Chapter 50: Pascal's Triangle
Section 50.1: Pascal triangle in C
int i, space, rows, k=0, count = 0, count1 = 0;
row=5;
for(i=1; i<=rows; ++i)
{
for(space=1; space <= rows-i; ++space)
{
printf(" ");
++count;
}

while(k != 2*i-1)
{
if (count <= rows-1)
{
printf("%d ", i+k);
++count;
}
else
{
++count1;
printf("%d ", (i+k-2*count1));
}
++k;
}
count1 = count = k = 0;

printf("\n");
}

Output

1
2 3 2
3 4 5 4 3
4 5 6 7 6 5 4
5 6 7 8 9 8 7 6 5

[Link] – Algorithms Notes for Professionals 231