 # Learn Data Structure and Algorithm in JavaScript | Part 03 Edison Pebojot(👨‍💻) Updated on ・18 min read

# Prerequisite (✋😐)

01 Big-O Notation By the end of this chapter, you will understand how to analyze an implementation of an algorithm with respect to both time (execution time) and space (memory consumed).
02 JavaScript Unique Parts Big-O is important for analyzing and comparing the efficiencies of algorithms. The analysis of Big-O starts by looking at the code, and, applying the rules, applying the rules is because to simplify the Big-O notation linear or quadratic rule is not enough.
03 JavaScript Numbers This part 3 will focus on JavaScript number operations, number representation, Number objects, common number algorithms, and random number generation.
04 JavaScript Strings This part 4 will focus on strings, JavaScript String object, and the String object’s built-in functions. You will learn how to access, compare, decompose, and search strings for commonly used real-life purposes. In addition, the chapter will explore string encoding, decoding, encryption, and decryption.
05 JavaScript Arrays As a JavaScript developer, you will use the array often; it is the most commonly used data structure. Arrays in JavaScript come with a lot of built-in methods. By the end of this part, you will understand arrays and choose the right method
06 JavaScript Object This part will focus on what JavaScript objects are, how they are declared, and how their properties can be changed. In addition, this part will cover how JavaScript classes are implemented using prototypal inheritance. Also this part will be short.
07 JavaScript Memory Management A variable takes up some memory. In C, the programmer allocate and deallocate memory manually. In contrast, modern JavaScript engines have garbage collectors that delete unused variables. However, there are pitfalls(unexpected) that developers can fall into(❗) This part will show these unexpected and present techniques to help the garbage collector minimize the memory problems.
08 Recursion This part 8 introduces the concept of recursion and recursive algorithms(Remember they are different, we will discuss them later(😉)). We will also discuss the definition of recursion and fundamental rules for recursive algorithms.
09 Sets This part focuses on the concepts of sets from both a mathematical definition and on the implementation. Also, Common set operations, as well as their implementations, are covered in great detail (💡).
10 Searching and Sorting This part 10 focuses on searching and sorting for arrays. By the end of this part 10, you will understand how to use sorting and searching algorithms for arrays. Also, this article is a bit complicated for beginners, so as much as possible the visual aids is your friend (👀). (😃)
11 Hash Tables A hash table is a fixed-sized data structure in which the size is defined at the start. This part 11 explains how hash tables work, and the method of generating a unique key. By the end of this part 11, you will understand various hashing techniques and know how to implement a hash table. (😃)
12 Stacks and Queues This part 12 covers stacks and queues(pronounce as kyooz (🔈)) not (kwewe) okay? hehehe (😅); both are data structures used in the implementation of complex data structures. You'll learn what the stacks and queues are, how they're used, when they're used, and how to implement them (😃) Let's go! (🔥🔥🔥)
13 Linked Lists A linked list is a data structure in which each node (or element) points to another node. Unlike arrays, which have a fixed size, a linked list is a dynamic data structure. By the end of this part 13, you will understand how to implement and work with linked lists. And oh! (😮) There are two types of linked lists: singly (➡️) and doubly (↔️). Let’s examine the singly linked list first.(😃) Let's go! (🔥🔥🔥)
14 Caching Caching is the process of storing data into temporary memory so that it can be easily retrieved for later use if it is required again. As an example, a database keeps data cached to avoid re-reading the hard drive, and a web browser caches web images to avoid re-downloading. In this part 14, two caching techniques will discussed: LFU and LRU caching.
15 Trees A general tree data structure is composed of nodes with children nodes. The top node is called the root node. This part 15 will explore different types of trees such as binary trees, binary search trees, and self-balancing binary search trees. First, this part 15 will cover what trees are and how they are structured. Then, it will cover methods of traversing(crossing or taking a zigzag path) the tree data structure in detail. Finally, you will learn about binary search trees and self-balancing binary search trees to understand how to store searchable data. (😃)
16 Heaps A heap is an important data structure that returns the highest or lowest element in O(1) time. This part 16 will focus on explaining how heaps are implemented as well as how to work with them. One example is heap sort, which is a sorting algorithm based on heaps.
17 Graphs In this Part 17, you will learn graph basics, including fundamental terminology and graph types. The Part 17 will also cover working with these different graph types and methods of representing graphs in data structures. Finally, algorithms for traversing, searching, and sorting graphs are explored to solve problems such as finding the shortest path between two graph nodes. (👍)
18 Advance Strings Part 18 will cover more complex string algorithms than covered in the previous section. Now that you have heard of certain other data models or structures, they should be easier to comprehend. Specifically, Part 18 will focus on string searching algorithms. (😉)
19 Dynamic Programming Dynamic programming involves breaking down problems into their subproblems. Solving the subproblems and saving those results into memory to access them whenever a repeated problem needs to be solved, the algorithmic complexity decreases significantly (⬇️). To explain dynamic programming, let’s re examine the Fibonacci sequence that was discussed in Part 8. Then Part 19 will cover the rules of dynamic programming and walk you through some examples to make the concepts more concrete. (😉)
20 Bit Manipulation Bit manipulation is an advanced topic that JavaScript developers typically do not need to know. However, you should learn a bit about bit manipulation if you want to implement high-performance server-side code. Understanding bit manipulation requires some knowledge of digital logic. Any introductory course in discrete math or circuits would be helpful to understand these concepts.

# Part 03: JavaScript Numbers(😱 🔥 🔢) This part 3 will focus on JavaScript number operations, number representation, Number objects, common number algorithms, and random number generation. By the end of this part, you will understand how to work with numbers in JavaScript as well as how to implement prime factorization, which is fundamental for encryption. (🔐)

Number operations allow you to compute numerical values. Here are the number operators in JavaScript:

+ : addition
- : subtraction
/ : division
* : multiplication
% : modulus


These operators are universally accepted in other programming languages and are not specific to JavaScript only.

### Number System (🔢) JavaScript uses a 32-bit floating-point representation for numbers. In this example, the value is 0.15625. The sign bit (31) indicates that the number is negative if the sign bit is 1. The next 8 bits indicate the exponent value, which is e. Finally, the remaining 23 bits represent the fraction value known as Mantissa (See on Wikipedia)  With the 32 bits, the value is computed by this esoteric formula (See on Reddit(r/math)):

$value=\lparen-1\rparen^{sign}\times2^{e-127}\times\lparen1+\displaystyle\sum_{t=1}^{23} b_{23-t}2^{-t}$

$e=\lparen 0111100\rparen_2 = 124\lparen in base 10\rparen$
$1+\displaystyle\sum_{i=1}^{23} b_{23-i}26{-i}=1+0+0.25+0$

This results in the following:

$value=1\times2^{124-127}\times1.25=1\times2^{-3}\times1.25=0.15625$

With decimal fractions, this floating-point number system causes some rounding errors in JavaScript. For example, 0.1 and 0.2 cannot be represented precisely. Hence, 0.1 + 0.2 === 0.3 yields false.

   (f=()=>0.1+0.2===0.3?true:false)() 

0.1 + 0.2 === 0.3; // prints 'false'


To really understand why 0.1 cannot be represented properly as a 32-bit floating-point number, you must understand binary (click here to learn more about binary). Representing many decimals in binary requires an infinite number of digits. This because binary numbers are represented by 2n where n is an integer.

While trying to calculate 0.1, long division will go on forever. As shown in __Figure 3-2, 1010 represents 10 in binary. Trying to calculate 0.1 (1/10) results in an indefinite number of decimal points. ## JavaScript Number Object (🔢) Luckily, there are some built-in properties of the Number object in JavaScript that help work around this. (😅)

### Integer Rounding (1️⃣1️⃣1️⃣1️⃣)

Since JavaScript uses floating point to represent all numbers, integer division in programming languages like Java simply evaluates division expressions to their quotient.

For example, 5/4 is 1 in Java because the quotient is 1(although there is a remainder):

public class Demo {
public static void main( String args[] ) {
int a = 5;
int b = 4;
System.out.println("a / b = " + (a / b) );
}
}


Output

5 / 4 = 1


However, in JavaScript, it is a floating point:

   (f=()=>5/4)() 
5/4 = 1.25


This is because Java requires you to explicitly type the integer as an integer. Hence, the result cannot be a floating point. However, if JavaScript developers want to implement integer division, they can do one of the following:

Math.floor // rounds down to nearest integer
Math.round // rounds to nearest integer
Math.ceil // rounds up to nearest integer
Math.floor(0.9); // 0
Math.floor(1.1); // 1
Math.round(0.49); // 0
Math.round(0.5); // 1
Math.round(2.9); // 3
Math.ceil(0.1); // 1
Math.ceil(0.9); // 1
Math.ceil(21); // 21
Math.ceil(21.01); // 22


### Number.EPSILON (3️⃣3️⃣)

Number.EPSILON returns the smallest interval between two representable numbers. This is useful for the problem with floating-point approximation.

   (numberEquals=()=>Math.abs(0.1 + 0.2-0.3) < Number.EPSILON)() // prints 'true' 

Output:

true


This function works by checking whether the difference between the two numbers are smaller than Number.EPSILON. Remember that Number.EPSILON is the smallest difference between two representable numbers. The difference between 0.1+0.2 and 0.3 will be smaller than Number.EPSILON. See the value of Number.EPSILON:

   (f=()=>Number.EPSILON)() 

Output:

2.220446049250313e-16


### Maximums (↗️↗️↗️)

Number.MAX_SAFE_INTEGER returns the largest integer:

   (f=()=>Number.MAX_SAFE_INTEGER + 1 === Number.MAX_SAFE_INTEGER + 2)() // prints 'true' 

Output:

true


This returns true because it cannot go any higher. However, it does not work for floating-point decimals:

   (f=()=>Number.MAX_SAFE_INTEGER + 1.111 === Number.MAX_SAFE_INTEGER + 2.022)() // prints 'false' 

Output:

false


Number.MAX_VALUE returns the largest floating-point number possible. Number.MAX_VALUE is equal to 1.7976931348623157e+308:

   (f=()=>Number.MAX_VALUE + 1 === Number.MAX_VALUE + 2)() // prints 'true' 

Output:

true


This uses double-precision floating-point representation and works for floating points as well:

   (f=()=>Number.MAX_VALUE + 1.111 === Number.MAX_VALUE + 2.022)() // prints 'true' 

Output:

true


### Minimums (👌👌👌)

Number.MIN_SAFE_INTEGER returns the smallest integer. Number.MIN_SAFE_INTEGER is equal to -9007199254740991:

   (f=()=>Number.MIN_SAFE_INTEGER - 1 === Number.MIN_SAFE_INTEGER - 2)() // prints 'true' 

Output:

true


This returns true because it cannot get any smaller. However, it does not work for floating-point decimals: (😈)

   (f=()=>Number.MIN_SAFE_INTEGER - 1.111 === Number.MIN_SAFE_INTEGER - 2.022)() // prints 'false' 

Output:

false


Number.MIN_VALUE returns the smallest floating-point number possible. Number.MIN_VALUE is equal to

$5\lparen e\rparen-324$

. This is not a negative number since it is the smallest floating-point number possible and means that Number.MIN_VALUE is actually bigger than Number.MIN_SAFE_INTEGER.

Number.MIN_VALUE is also the closest floating point to zero:

   (f=()=>Number.MIN_VALUE - 1 == -1)() // prints 'true' 

Output:

true


This is because this is similar to writing 0 - 1 == -1.

#### Infinity (🌀🌀🌀🌀)

The only thing greater than Number.MAX_VALUE is Infinity, and the only thing smaller than Number.MAX_SAFE_INTEGER is -Infinity(negative infinity):

   let i=()=>Infinity > Number.MAX_SAFE_INTEGER // true let j=()=>-Infinity < Number.MAX_SAFE_INTEGER // true let k=()=>-Infinity-32323323 == -Infinity-1 // true i();j();k() 

Output:

true


This evaluates to true because nothing can go smaller or higher to -Infinity. (😎)

### Size Summary ( $\lparen=\rparen$ )

This summarizes the size of JavaScript numbers from the smallest left (⬅️) to the largest right (➡️):

-Infinity < Number.MIN_SAFE_INTEGER < Number.MIN_VALUE < 0 < Number.MAX_SAFE_INTEGER < Number.MAX_VALUE < Infinity

   (f=()=>-Infinity < Number.MIN_SAFE_INTEGER < Number.MIN_VALUE < 0 < Number.MAX_SAFE_INTEGER < Number.MAX_VALUE < Infinity)() // prints 'true' 

Output:

true


### Number Algorithms: (⤵️↩️⤴️↪️)

One of the most discussed algorithms involving numbers is for testing whether a number is a prime number or not. Let’s review this now❗

#### Primary Test (🔬🔬🔬)

A primary test can be done by iterating from 2 to n, checking whether modulus division (remainder) is equal to zero: 0️⃣

   // List of Prime Number ... // 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97 function isPrime(n){ if (n <= 1) { return false; } // check from 2 to n-1 for (var i=2; i<n; i++) { if (n%i == 0) { return false; } } return true; } isPrime(2) // Change the value 

Time Complexity: $O\lparen n \rparen$

The time complexity is $O\lparen n \rparen$ because this algorithm checks all numbers from $0$ to ${n}$ . Always remember this term, as we will use this in more advance part, the search and sorting algorithm. Okay, think about how this method iterates through $2$ to ${n}$ .

Is it possible to find a pattern to make the algorithm
faster?
(❓❓😨😨)

First, any multiple of 2s can be ignored. Here's a list some prime numbers:

$2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97$

This is difficult to notice, but all primes are of the form $6 \times k \pm 1$ , with the exception of $2$ and $3$ where $k$ is some integer. Here’s an example:

5 = (6-1) , 7 = ((1*6) + 1), 13 = ((2*6) + 1) etc


Also realize that for testing the prime number n, the loop only has to test the square root of n. This is because if the square root of n is not a prime number, n is not a prime number by mathematical definition: (:thumbsup:)

function isPrime(n){
if (n <= 1) return false;
if (n <= 3) return true;

// This is checked so that we can skip
// middle five numbers in below loop
if (n%2 == 0 || n%3 == 0) return false;

for (var i=5; i*i<=n; i=i+6){
if (n%i == 0 || n%(i+2) == 0)
return false;
}

return true;
}

**Time Complexity:** {% katex inline %} O\lparen sqrt(n) \rparen {% endkatex %}
This improved solution cuts the time complexity down significantly.



Test it here: (😐😐😐)

   // Put your code here to test 

### Prime Factorization: (📐📐📐)

Another useful algorithm to understand is for determining prime factorization of a number. Prime numbers are the basis of encryption (which we will covered in part 4) and hashing (which we will also covered in part 11), and prime factorization is the process of determining which prime numbers multiply to a given number:

   function primeFactors(n){ // Print the number of 2s that divide n while (n % 2 == 0) { console.log(2); n = n / 2; } // n must be odd at this point. So we can skip one element // (Note i = i + 2) for (var i = 3; i * i <= n; i = i + 2) { // While i divides n, print i and divide n while (n % i == 0) { console.log(i); n = n / i; } } // This condition is to handle the case when n is a prime number // greater than 2 if (n > 2) { return n; } } primeFactors(10); // prints '5' and '2' 

Time Complexity: $O\lparen sqrt(n) \rparen$
This algorithm works by printing any number that is divisible by i without a remainder. In the case that a prime number is passed into this function, it would be handled by printing whether n is greater than 2. (👈)

### Random Number Generator:(➿➿➿) JavaScript has a built-in function for generating numbers: Math.random().

Note(📝):Math.random() returns a float between 0 and 1.

To get floating points higher than 1 (⬆️⬆️), simply multiply Math.random() by the range:

   let i=()=>Math.random() * 100 // floats between 0 and 100 let j=()=>Math.random() * 25 + 5 // floats between 5 and 30 let k=()=>Math.random() * 10 - 100 // floats between -100 and -90 console.log("i="+i()) console.log("j="+j()) console.log("k="+k()) 

Simply use Math.floor(), Math.round(), or Math.ceil() to round to an integer: (😎😎)

   let i=()=>Math.floor(Math.random() * 100) // integer between 0 and 99 let j=()=>Math.round(Math.random() * 25) + 5 // integer between 5 and 30 let k=()=>Math.ceil(Math.random() * 10) - 100 // integer between -100 and -9k console.log("i="+i()) console.log("j="+j()) console.log("k="+k()) 

# Summary (📚) Recall that all numbers in JavaScript are in 32-bit floating point format. To get the smallest possible floating point, you should use Number.EPILSON. The maximum and minimum numbers of JavaScript can be summarized by the following inequality:

-Infinity < Number.MIN_SAFE_INTEGER < Number.MIN_VALUE < 0
< Number.MAX_SAFE_INTEGER < Number.MAX_VALUE < Infinity


Prime number validation and prime factorization are concepts used i n various computer science applications such as encryption, which we will covered in part 4. Finally, random number generation in JavaScript works via Math.random(). Okay! (🔥)

# Challenge (😤😤😤) Have some time to solve this riddle while waiting for part 4. However, there is sample code and explanation, solve this on your own, and have your own code other than the code and explanation provided below, I don't want to see your answer or explanation (or if you want to show it all right, just make sure to share it in the comment: (😅)

1. Given three numbers x, y, and p, compute(This is modular exponentiation): (x^y) % p

Explanation:

Here, x is the base, y is exponent, and p is the modulus.

Modular exponentiation is a type of exponentiation performed over a modulus, which is useful in computer science and used in the field of public-key encryption algorithms.

At first, this problem seems simple. Calculating this is a one-line solution, as shown here:

let modularExponentiation=( base, exponent, modulus )=>Math.pow(base,exponent) % modulus


Note(📝): This does exactly what the question asks. However, it cannot handle large exponents.

Remember that this is implemented with encryption algorithms.
In strong cryptography, the base is often at least 256 bit (78 digits).

Consider this case, for example:

Base: 6*1077, Exponent: 27, Modulus: 497

In this case, (6*10^77)^27 is a very large number and cannot be stored in a 32-bit floating point.

There is another approach, which involves some math. One must
observe the following mathematical property:

For arbitrary a and b,

c % m = (a b) % m
c % m = [(a % m) (b % m)] % m


Using this mathematical property, you can iterate 1 to the
exponent, recalculating each time by multiplying the current
modulus value with the last.

Here is the pseudocode:

1. Set value = 1, current exponent = 0.
2. Increment current exponent by 1.
3. Set value = (base value) mod modulus until current exponent is reached exponent

Example: Base: 4, Exponent: 3, Modulus: 5

4ˆ3 % 5 = 64 % 5 = 4

value = (lastValue x base ) % modulus:

value = (1 x 4) % 5 = 4 % 5 = 4

value = (4 x 4) % 5 = 16 % 5 = 1

value = (1 x 4) % 5 = 4 % 5 = 4


Finally, here is the code:

function modularExponentiation ( base, exponent, modulus ) {
if (modulus == 1) return 0;

var value = 1;

for ( var i=0; i<exponent; i++ ){
value = (value * base) % modulus;
}
return value;
}


Time Complexit: O(n)

The time complexity is O(n) where n is equal to the exponent value.

1. Print all primes less than n

Explanation:
To do this, use the isPrime function covered in this part 3.
Simply iterate from 0 to n and print any prime numbers where
isPrime() evaluates to true.

function allPrimesLessThanN(n) {
for (var i = 0; i < n; i++) {
if (isPrime(i)) {
console.log(i);
}
}
}
function isPrime(n) {
if (n <= 1) return false;
if (n <= 3) return true;

// This is checked so that we can skip
// middle five numbers in below loop
if (n % 2 == 0 || n % 3 == 0) return false;

for (var i = 5; i * i <= n; i = i + 6) {
if (n % i == 0 || n % (i + 2) == 0)
return false;
}

return true;
}

allPrimesLessThanN(15);

// prints 2, 3, 5, 7, 11, 13


Time Complexity: O(nsqrt(n))

This is because isPrime (covered earlier in this chapter) with a
time complexity of O(sqrt(n)) is run n times.

1. Check for a set of prime factors.

Explanation:

Let’s define ugly numbers as those whose only prime factors are
2, 3, or 5. The sequence 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, … shows the first 11 ugly numbers. By convention, 1 is included.

To do this, divide the number by the divisors (2, 3, 5) until it
cannot be divided without a remainder. If the number can be divided by all the divisors, it should be 1 after dividing everything.

function maxDivide(number, divisor) {
while (number % divisor == 0) {
number /= divisor;
}
return number;
}

function isUgly(number) {
number = maxDivide(number, 2);

number = maxDivide(number, 3);
number = maxDivide(number, 5);
return number === 1;
}


Iterate this over n, and now the list of ugly numbers can be
returned:

function arrayNUglyNumbers (n) {
var counter = 0, currentNumber = 1,
uglyNumbers = [];
while ( counter != n ) {
if (isUgly(currentNumber) ) {
counter++;
uglyNumbers.push(currentNumber);
}

currentNumber++;
}

return uglyNumbers;
}


Time Complexity for maxDivide(number, divisor):
O(log_divisor(number))

The time complexity of maxDivide is a logarithmic function which
depends on divisor and the number. When testing primes of 2,
3, and 5, the logarithmic of 2(log_2(n)) yields the highest time
complexity.

Time Complexity for isUgly: O(log_2(n))

Time Complexity for arrayNUglyNumbers: O(n(log_2(n)))

The isUgly function is limited by the time complexity of maxDivide(number, 2). Hence, arrayNUglyNumbers has n times that time complexity.

# Up Next👉 Part 04: JavaScript Strings 🔥 🔥 (July 05, 2020) Posted on by: ### Edison Pebojot(👨‍💻)

I started using computers and writing software around 2008 and 2009, I taught myself Programming. However, I wasn't a typical "nerd-klutz". 😅

### Discussion Pretty in depth, but no mention of BigInts?  