loading...
Cover image for Learn Data Structure and Algorithm in JavaScript | Part 03

Learn Data Structure and Algorithm in JavaScript | Part 03

edisonnpebojot profile image Edison Pebojot(๐Ÿ‘จโ€๐Ÿ’ป) Updated on ใƒป18 min read


Prerequisite (โœ‹๐Ÿ˜)

If you're reading this article right now, please considered to read our Part 01: Big-O Notation and Part 02: JavaScript Unique Part

Part Table of Contents Description
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(๐Ÿ˜ฑ ๐Ÿ”ฅ ๐Ÿ”ข)

Alt Text

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
Enter fullscreen mode Exit fullscreen mode

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

Number System (๐Ÿ”ข)

alt text
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)

Alt Text
alt text

Figure 3-1. The 32-bit floating-point number system

With the 32 bits, the value is computed by this esoteric formula (See on Reddit(r/math)):

value=(โˆ’1)signร—2eโˆ’127ร—(1+โˆ‘t=123b23โˆ’t2โˆ’t value=\lparen-1\rparen^{sign}\times2^{e-127}\times\lparen1+\displaystyle\sum_{t=1}^{23} b_{23-t}2^{-t}

Figure 3-1 shows the following break down of the 32 bits (Click here to learn more about base 10):

e=(0111100)2=124(inbase10) e=\lparen 0111100\rparen_2 = 124\lparen in base 10\rparen
1+โˆ‘i=123b23โˆ’i26โˆ’i=1+0+0.25+0 1+\displaystyle\sum_{i=1}^{23} b_{23-i}26{-i}=1+0+0.25+0

This results in the following:

value=1ร—2124โˆ’127ร—1.25=1ร—2โˆ’3ร—1.25=0.15625 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'
Enter fullscreen mode Exit fullscreen mode

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.

alt text

Figure 3-2. Long division for 0.1

JavaScript Number Object (๐Ÿ”ข)

alt text
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) );
   }
}
Enter fullscreen mode Exit fullscreen mode

Output

5 / 4 = 1
Enter fullscreen mode Exit fullscreen mode

However, in JavaScript, it is a floating point:

(f=()=>5/4)()
5/4 = 1.25
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

Maximums (โ†—๏ธโ†—๏ธโ†—๏ธ)

Number.MAX_SAFE_INTEGER returns the largest integer:

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

Output:

true
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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

5(e)โˆ’3245\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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode
(f=()=>-Infinity < Number.MIN_SAFE_INTEGER < Number.MIN_VALUE < 0 < Number.MAX_SAFE_INTEGER < Number.MAX_VALUE < Infinity)() // prints 'true'

Output:

true
Enter fullscreen mode Exit fullscreen mode

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(n)O\lparen n \rparen

The time complexity is O(n)O\lparen n \rparen because this algorithm checks all numbers from 00 to n{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 22 to n{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 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ร—kยฑ16 \times k \pm 1 , with the exception of 22 and 33 where kk is some integer. Hereโ€™s an example:

5 = (6-1) , 7 = ((1*6) + 1), 13 = ((2*6) + 1) etc
Enter fullscreen mode Exit fullscreen mode

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.

Enter fullscreen mode Exit fullscreen mode

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(sqrt(n))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:(โžฟโžฟโžฟ)

alt text
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 (๐Ÿ“š)

alt text
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
Enter fullscreen mode Exit fullscreen mode

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 (๐Ÿ˜ค๐Ÿ˜ค๐Ÿ˜ค)

alt text

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

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;
   }
Enter fullscreen mode Exit fullscreen mode

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)


alt text

Posted on by:

edisonnpebojot profile

Edison Pebojot(๐Ÿ‘จโ€๐Ÿ’ป)

@edisonnpebojot

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

Discussion

pic
Editor guide
 

Pretty in depth, but no mention of BigInts?