DEV Community: Rusu Emanuel

Binary search trees🌳

Rusu Emanuel — Sun, 24 Jul 2022 13:35:00 +0000

👋Heeelloo everybody! 🔥🚀

-> This post is about binary search trees🌳. They are represented by nodes linked together to simulate a hierarchy, and these nodes are positioned following a rule.

-> I will walk you through the implementation of a binary search tree. Working with trees requires knowledge about pointers, the memory layout of a C program, memory allocation, and a good understanding of recursion.

-> We focus on binary search tree🌳 because this is a time-efficient data structure. We call it binary because every node can have at most two children. It is a search tree because it respects a particular condition which says that every node with a value smaller than the root node is going to be placed on the left of the root node, and every node with a value bigger than the root node is going to be placed in the right of the root node. This rule is applied recursively for every right subtree and left subtree.

-> Searching, accessing, inserting, and deleting in a binary search tree🌳 are usually done in O(log n). But there is a chance that a binary search tree can have a structure similar to a linked list, and the operations mentioned above will be done in O(n). This situation is a drawback for the tree data structure and it happens when every new node has either a smaller value than the last node, or a bigger value than the last node. Try to draw a binary search tree with these values: 10, 9, 8, 7, 6, 5, 4 and with these values: 4, 5, 6, 7, 8, 9, 10 and see what happens.

-> Happily, another tree🌳 data structure, AVL, is an improvement of classical trees. AVL is a self-balancing tree, and by balancing, we avoid the situation when the tree can become a linked list. But this is another discussion.

-> We can implement trees with more than two children, but time complexity will not change. Only the logarithm base will change, but it doesn't matter in complexities, so again, the time complexity will be O(log n) in the best case and O(n) in the worst case.

1. First step: creating a `Node` data type

To work with a tree data structure, we need to create a new data type, a Node data type. Trees🌳 use nodes. Here we define our Node data type as having three attributes: an unsigned long long variable - representing the information to be stored(also it can be any primitive or abstract data type. I used a primitive data type for simplicity), a reference to the left child, and a reference to the right child.


struct Node
{
    unsigned long long data;
    Node* left;
    Node* right;
};

2. Second step: generating `Node` variables

After we define how a Node data type looks, we need to be able to create variables of that type. We are working with heap memory, so we must dynamically allocate memory for our new nodes—the new operator requests memory of the size of our data type. Then we initialize data attribute and references. The nullptr keyword was introduced in C++, representing 0 as an adress and only as an adress; nullptr is a keyword with pointer type. On the other hand, NULL is by default 0 and is not always a pointer. I will post about the difference between nullptr and NULL in the future. Because we are working with pointers and we are in C++, is better to use nullptr.


Node* CreateNode(unsigned long long Data)
{
    Node* newNode = new Node;

    newNode->data = Data;
    newNode->left = nullptr;
    newNode->right = nullptr;

    return newNode;
}

3. Third step: inserting nodes

After we defined how our Node data type looks and we made sure that we can create variables of that type, we need to be able to put these variables in such a way that respects the definition of a binary search tree. We will create a function for inserting in a binary search tree. I prefer the recursive method as it is shorter. We need two arguments for that function: the root node and the information/object to be stored. If the root is null, then we know that it is time to create a new Node variable and insert it. If the value of information/object is greater than the value of the actual root node, then we go to the right; if not, then we go to the left.


void InsertNode(Node*& Root, unsigned long long Data)
{
    if (Root == nullptr) Root = CreateNode(Data);
    else if (Data > Root->data) InsertNode(Root->right, Data);
    else InsertNode(Root->left, Data);
}

4. Fourth step: printing a binary search tree

We created a Node data type, and we made sure that we could generate Node variables and we made sure that we could insert them correctly. Now we need to think about how we can see our data structure. For this, we need to use algorithms for depth traversals or breadth traversal. There are four possible algorithms: inorder, preorder, postorder and level order traversal. I use preorder for this example.


void Print(Node* Root)
{
    if (Root)
    {
        cout << Root->data << ' ';
        Print(Root->left);
        Print(Root->right);
    }
}

We are done. We have all pieces for working with a binary search tree.
Here is the complete code🔥:


#include <iostream>
using namespace std;


struct Node
{
    unsigned long long data;
    Node* left;
    Node* right;
};


Node* CreateNode(unsigned long long Data)
{
    Node* newNode = new Node;

    newNode->data = Data;
    newNode->left = nullptr;
    newNode->right = nullptr;

    return newNode;
}


void InsertNode(Node*& Root, unsigned long long Data)
{
    if (Root == nullptr) Root = CreateNode(Data);
    else if (Data > Root->data) InsertNode(Root->right, Data);
    else InsertNode(Root->left, Data);
}


void Print(Node* Root)
{
    if (Root)
    {
        cout << Root->data << ' ';
        Print(Root->left);
        Print(Root->right);
    }
}


int main()
{
    Node* root = nullptr;
    unsigned long long i = 0, nodesNumber;
    cout << "Number of nodes to be added: "; cin >> nodesNumber; cout << '\n';

    while (i < nodesNumber)
    {
        unsigned long long number; cout << "Value of node: "; cin >> number; cout << '\n';
        InsertNode(root, number);
        ++i;
    }

    cout << "Binary search tree printed: "; Print(root);
    cout << '\n';

    return 0;
}

This is a basic structure. I wanted to give you the main idea. We can also create a Tree🌳 data type and think about Tree🌳 as an object with attributes rather than a simple variable called root. But from here, you can improve/change this implementation as you like. Feel free to explore.🗺️ and be curious.

❗Observations:

I focused on the idea rather than on a real-world scenario where I must consider validations and other stuff.
I have used C++ programming language.

Emanuel Rusu👨‍🎓
You can visit my GitHub
Or you can find me on Linkedin
Next topic: Intern reprezentation of primitive data types
See you next time! 👋

Sieve of Eratosthenes

Rusu Emanuel — Fri, 10 Jun 2022 18:13:00 +0000

Heeelloooo everyone!🔥😎

As I told you in the previous post, I am going to write about the Sieve of Eratosthenes. Commonly, this algorithm comes together with the primality of a number problem. It is used in contests, websites with algorithmic problems, competitive programming, Olympiads, and maybe at university admission competitions. Sieve of Eratosthenes finds all prime numbers between an interval. It is a time-efficient algorithm because instead of checking all numbers between a given interval, we can mark some numbers as not primes without even checking them. This way, we avoid unnecessary analyses.
On the other hand, it is not a space-efficient algorithm. We have to keep track of numbers marked as not primes and numbers marked as primes if we don't store this information (number, marked/unmarked) we can't implement the Sieve of Eratosthenes idea. Enough introduction. Let's dig in.

Problem to solve: Print all prime numbers between 2 and n.

Idea🤔

We have to analyze numbers from 2 to n. Firstly, we write them down:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 ... n

Next, we will do something which is called marking. To illustrate this, I will use strikethrough digits. A strikethrough digit means a marked number, so not a prime number; a simple number means an unmarked number, so a prime number.

Then we begin from 2 till n, and for every number, we mark all its multiples till n inclusive.

We are at 2, so we mark 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26 and all numbers 2 * k, with k > 1 and stop when 2 * k > n.

2 3 ̷4 5 ̷6 7 ̷8 9 ̷1̷0 11 ̷1̷2 13 ̷1̷4 15 ̷1̷6 17 ̷1̷8 19 ̷2̷0 21 ̷2̷2 23 ̷2̷4 25 2̷6 ... n

We move at 3 so we mark 6, 9, 12, 15, 18, 21, 24 and all numbers 3 * k, with k > 1 and stop when 3 * k > n.

2 ̷3 ̷4 5 ̷6 7 ̷8 ̷9̷ ̷1̷0 11 ̷1̷2 13 ̷1̷4 ̷1̷5 ̷1̷6 17 ̷1̷8 19 ̷2̷0 ̷2̷1 ̷2̷2 23 ̷2̷4 25 2̷6 ... n

We continue this process by taking every number till n and marking all its multiples till n inclusive.

By the end of this algorithm, the numbers that remained unmarked are only prime numbers.

Let's take an example:

Let's find all prime numbers until 22(n).

List all numbers till n = 22:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

Start from 2 and mark all its multiples smaller or equal than 22.

2 3 ̷4 5 ̷6 7 ̷8 9 ̷1̷0 11 ̷1̷2 13 ̷1̷4 15 ̷1̷6 17 ̷1̷8 19 ̷2̷0 21 ̷2̷2

Move to 3 and mark all its multiples smaller or equal than 22.
2 3 ̷4 5 ̷6 7 ̷8 ̷9̷ ̷1̷0 11 ̷1̷2 13 ̷1̷4 ̷1̷5 ̷1̷6 17 ̷1̷8 19 ̷2̷0 ̷2̷1 ̷2̷2

If we want to move to 4, we can see that it's multiples smaller
than 22 are already marked, similarly with 5, 6, 7, ...,
22.

2 3 ̷4 5 ̷6 7 ̷8 ̷9̷ ̷1̷0 11 ̷1̷2 13 ̷1̷4 ̷1̷5 ̷1̷6 17 ̷1̷8 19 ̷2̷0 ̷2̷1 ̷2̷2

Write down unmarked numbers: 2 3 5 7 11 13 17 19

Done!
Congratulations!🥳 You found all primes numbers using the Sieve of Eratosthenes algorithm.

Maybe you want to see the code but let me explain it before.👨‍🏫

First, I will use a straightforward algorithm and then optimize it as we go deeper and deeper.

As I said in the beginning, we need to write down the numbers from 2 to n. We do that by using a boolean array like this:

#define MAX 1000000001
bool sieve[MAX];

Why do we use such a big number? Because we don't know how big the interval is, we give as much freedom as possible; note that this number may not work for your computer, and you will need to make it smaller.

Then I said that we needed to mark numbers somehow. In Sieve of Eratosthenes, we use a global array, and global variables are automatically initialized with 0. We use that to our advantage instead of a for to set all memory spaces manually with 0.

We are doing marking like this:

0 - prime
1 - not prime

Why? I know that using 1 for primes and 0 for not primes would have been more intuitive but declaring an array in global scope, it got initialized with 0, so it is just a waste to overwrite all memory spaces with 1.

Then we mark in advance 0 and 1 because we know these numbers are not prime.

sieve[0] = sieve[1] = 1;

Now we start to iterate from 2 till n.

for (unsigned long long i = 2; i <= n; ++i)

For every i, we mark all its multiples smaller or equal than n.

for (unsigned long long j = 2; j <= n / i; ++j) sieve[i * j] = 1;

We iterate till n / i because this division gave us the biggest number, which can be multiplied by j, which is smaller or equals to n, so iterating till this number, we can guarantee that we marked all multiples of i smaller than n. sieve[i * j] is the multiple of i.

The last thing we have to do is to iterate the interval and print all unmarked values. We do that by asking if sieve[i] == 0 in a for loop like this:

    for (unsigned long long i = 2; i <= n; ++i)
    {
        if (sieve[i] == 0) cout << i << ' ';
    }

The first version of our algorithm is done:


#include <iostream>
using namespace std;


#define MAX 1000000001
bool sieve[MAX];


void PrintSieveofEratosthenes(unsigned long long n)
{
    for (unsigned long long i = 2; i <= n; ++i)
    {
        if (sieve[i] == 0) cout << i << ' ';
    }
}


void SieveofEratosthenes(unsigned long long n)
{
    sieve[0] = sieve[1] = 1;

    for (unsigned long long i = 2; i <= n; ++i)
    {
        for (unsigned long long j = 2; j <= n / i; ++j) sieve[i * j] = 1;
    }

}


int main()
{
    unsigned long long n; cin >> n;
    SieveofEratosthenes(n);
    PrintSieveofEratosthenes(n);

    return 0;
}

I like to refactor this a bit. I consider that the function call for printing is a bit unnecessary because we can print numbers inside the first loop. We know that if sieve[i] == 0 we found a prime number. Here is another version that I like more:


#include <iostream>
using namespace std;


#define MAX 1000000001
bool sieve[MAX];


void SieveofEratosthenes(unsigned long long n)
{
    sieve[0] = sieve[1] = 1;

    for (unsigned long long i = 2; i <= n; ++i)
    {
        for (unsigned long long j = 2; j <= n / i; ++j) sieve[i * j] = 1;

        if (sieve[i] == 0) cout << i << ' ';
    }
}


int main()
{
    unsigned long long n; cin >> n;
    SieveofEratosthenes(n);

    return 0;
}

Now we get into optimizations. Sieve of Eratosthenes is more than two loops. If you read till now, congratulations!🥳

We know that every even number greater than 2 is not prime. We can mark in advance these numbers by beginning from 4 and iterating from 2 to 2.

for(unsigned long long i = 4; i <= n; i += 2) sieve[i] = 1;

Because we marked even numbers before, we don't need to analyse them again so we can start from i = 3 and increment it by 2. This way we take into consideration only odd numbers.

Then we can iterate only till √n using i * i <= n.


    sieve[0] = sieve[1] = 1;
    for (unsigned long long i = 4; i <= n; i += 2) sieve[i] = 1;

    for (unsigned long long i = 3; i * i <= n; i += 2)
    {
        for (unsigned long long j = 2; j <= n/i; ++j) sieve[i*j] = 1;
    }

We can optimize how we iterate through multiples of every number. We can begin from i * i because all numbers till i * i have been already marked; and increment j with i.


    sieve[0] = sieve[1] = 1;
    for (unsigned long long i = 4; i <= n; i += 2) sieve[i] = 1;

    for (unsigned long long i = 3; i * i <= n; i += 2)
    {
        for (unsigned long long j = i * i; j <= n; j+=i) sieve[j] = 1;
    }

We can iterate with j += 2 * i to ignore odd numbers.


    sieve[0] = sieve[1] = 1;
    for (unsigned long long i = 4; i <= n; i += 2) sieve[i] = 1;

    for (unsigned long long i = 3; i * i <= n; i += 2)
    {
        for (unsigned long long j = i * i; j <= n; j += 2 * i) sieve[j] = 1;
    }

Here is the final code:

#include <iostream>
using namespace std;

#define MAX 1000000001
bool sieve[MAX];


void PrintSieveofEratosthenes(unsigned long long n)
{
    for (int i = 2; i <= n; ++i)
    {
        if (sieve[i] == 0) cout << i << ' ';
    }
}


void SieveofEratosthenes(unsigned long long n)
{
    sieve[0] = sieve[1] = 1;

    for (unsigned long long i = 4; i <= n; i += 2) sieve[i] = 1;

    for (unsigned long long i = 3; i * i <= n; i += 2)
    {
        for (unsigned long long j = i * i; j <= n; j += 2* i) sieve[j] = 1;
    }
}


int main()
{
    unsigned long long n; cin >> n;
    SieveofEratosthenes(n);
    PrintSieveofEratosthenes(n);

    return 0;
}

This block of code gives time complexity:

for (unsigned long long i = 3; i * i <= n; i += 2)
{
    for (unsigned long long j = i * i; j <= n; j += 2 * i) sieve[j] = 1;
}

The first loop performs √n operations because we iterate till i * i <= n. The idea of the second loop is to mark all multiples of i. So, it will perform n / i steps. It is a known formula that if you want to find out how many divisors of a number till n are, you divide n / your_number. So for every i we will perform n / i steps. (technically, we perform fewer steps because I increased j with 2 * i to avoid iterating through even multiples of i, but ignore that. What I did is not enough to decrease the order of complexity anyway).

For every i till √n we perform n / i operations, where i is prime.

The ecuation is:
√n * (n/3 + n/4 + n/5 + n/6 + n/7 + ...)
= √n * n * (1/3 + 1/4 + 1/5 + 1/6 + 1/7 + ...)
The third factor, according to Euler grows the same as ln(ln(n))
So the time complexity is: O(√n * n * ln(ln(n))).

Observations❗:

Note that I used unsigned long long for variables, and operations like raising to power can easily exceed unsigned long long, so be careful with input numbers.
You can play around with #define MAX 1000000001 and #define MAX_PRIMES 100000001. Try to find which is the maximum limit accepted by your computer.
To make this algorithm space-efficient, you can use a vector container from the STL library like this vector <bool> vector_name. Before that, include vector library like #include <vector>. That container is not a regular one. It is a memory-optimization of template classes like vector <T>, which uses only n/8 bytes of memory. Many modern processors work faster with bytes because they can be accessed directly. vector <T> template class works directly with bits. But these things require knowledge about template classes, which are very powerful in C++.
This algorithm can be optimized even more using bits operations to achieve linear time. But ln(ln(n)) can be approximated to O(1).

And here is the bonus algorithm for testing primality I spoke about in the post before(probably the fastest for checking primality)🏎️:

#include <iostream>
using namespace std;


#define MAX 1000000001
#define MAX_PRIMES 100000001
bool sieve[MAX];
unsigned long long primeNumbers[MAX_PRIMES];


void SieveofEratosthenes(unsigned long long n)
{
    sieve[0] = sieve[1] = 1;

    for (unsigned long long i = 4; i <= n; i += 2) sieve[i] = 1;

    for (unsigned long long i = 3; i * i <= n; i += 2)
    {
        for (unsigned long long j = i * i; j <= n; j += 2 * i) sieve[j] = 1;
    }


    unsigned long long k = 0;
    for (int i = 2; i <= n; ++i)
    {
        if (sieve[i] == 0) primeNumbers[k++] = i;
    }
}


bool IsPrime(unsigned long long Number)
{
    unsigned long long k = 0;

    while (Number > 1)
    {
        unsigned long long power = 0;

        if (Number % primeNumbers[k] == 0)
        {
            Number /= primeNumbers[k];
            ++power;
        }

        if (power) return false;

        ++k;

        if (primeNumbers[k] * primeNumbers[k] > Number) return true;
    }
}


int main()
{
    unsigned long long number; cout << "Enter number: "; cin >> number; cout << '\n';
    SieveofEratosthenes(number);

    IsPrime(number) == 1 ? cout << "Prime\n" : cout << "Not prime\n";

    return 0;
}

Emanuel Rusu
You can visit my GitHub
Or you can find me on [Linkedin]
Rusu Emanuel
Next topic: Binary search trees🌳
See you next time ! 👋

Algorithms for primes number - introduction

Rusu Emanuel — Wed, 25 May 2022 22:00:52 +0000

Heellooo everybody🔥, Welcome back! 😎

Determining if a number is prime is a common problem in high school, the Olympics, and some contests or websites with algorithmic problems. Mathematicians have a high focus on prime numbers, they are really useful in cryptography area and in math in general. Being a prime number is a property studied in number theory, a really nice chapter for computer science which I will talk about in future posts.

There are plenty of solutions. All solutions return the correct answer, but the difference is their time and space complexity, a core concept in programming. We always search for the most efficient approach. I don’t want to cover complexity analysis in this post, but I will briefly present some complexities.

The first algorithm is:

#include <iostream>
using namespace std;


bool IsPrime(unsigned long long Number)
{
    unsigned long long cnt{ 0 };

    for (unsigned long long i = 1; i <= Number; ++i)
    {
        if (Number % i == 0) ++cnt;
    }

    if (cnt >= 3) return 0;

    return 1;
}


int main()
{

    unsigned long long number; cout << "Enter number: "; cin >> number; cout << '\n';

    IsPrime(number) == 1 ? cout << "Prime\n" : cout << "Not prime\n";

    return 0;
}

This is the most basic solution. It follows exactly the mathematically definition of prime numbers - A prime number has exactly two divisors. We iterate from 1 until we reach our number, trying to find how many divisors exist. If there are more than 2, we return 0(false) or 1(true) if the number of divisors is smaller than 2. It is a good approach if you are new to algorithms.

We iterate the whole interval between 1 and the number passed as argument. This gave us a linear complexity, O(n). Although this sounds good, we make some useless analyses for some numbers.

The first optimization we can do is to stop right when we find that there are more than two divisors, so our solution will look like this:

#include <iostream>
using namespace std;


bool IsPrime(unsigned long long Number)
{
    unsigned long long cnt{ 0 };

    for (unsigned long long i = 1; i <= Number; ++i)
    {
        if (Number % i == 0) ++cnt;

        if (cnt >= 3) return 0;
    }

    return 1;
}


int main()
{

    unsigned long long number; cout << "Enter number: "; cin >> number; cout << '\n';

    IsPrime(number) == 1 ? cout << "Prime\n" : cout << "Not prime\n";

    return 0;
}

Our complexity still doesn't decrease, but it is worth optimization, which makes our code better.

We can continue our improvements by not beginning to iterate from 1 because we know that 1 is the divisor for any number. Also, we can only iterate till the half of the number because we count for its divisors, and divisors of a number can be found till the half of the number. In this case, we can get rid of the divisor's counter because we start from 2 and stop at half, so it is enough to find only one divisor to say that the number is not prime. So our code will look like this:

#include <iostream>
using namespace std;


bool IsPrime(unsigned long long Number)
{
    for (unsigned long long i = 2; i <= Number / 2; ++i)
    {
        if (Number % i == 0) return 0;
    }

    return 1;
}


int main()
{

    unsigned long long number; cout << "Enter number: "; cin >> number; cout << '\n';

    IsPrime(number) == 1 ? cout << "Prime\n" : cout << "Not prime\n";

    return 0;
}

Spoiler alert, our time complexity didn’t change. It is still a linear algorithm.
Why?
Because we make O(n/2) steps, and if we rewrite this like O(1/2 * n), 1/2 is constant, and we don’t care about constants, so we remove them, and we have O(n).

Another optimization is to iterate till the square root of the number. We know that divisors of a number are in pairs, so if we don’t find divisors between [2, square root of the number], we will not find any divisors from the [square root of the number, number]. The code will look like this:

#include <iostream>
using namespace std;


bool IsPrime(unsigned long long Number)
{
    for (unsigned long long i = 2; i * i <= Number; ++i)
    {
        if (Number % i == 0) return 0;
    }

    return 1;
}


int main()
{

    unsigned long long number; cout << "Enter number: "; cin >> number; cout << '\n';

    IsPrime(number) == 1 ? cout << "Prime\n" : cout << "Not prime\n";

    return 0;
}

Now, the time complexity has changed. It became O(sqrt(n)) because we iterate over sqrt(n) numbers. Even if we exclude 1, which will be O(sqrt(n) - 1), 1 is constant, so we don’t care. Thus we remove it.

Note that we used i * i <= n instead of using sqrt(n). This is because sqrt(n) is a function which require time to complete and we prefer to avoid this time taken by calling sqrt(n). Even worse will be to write the for loop like this for (unsigned long long i = 1; i <= sqrt(Number); ++i). Writting code like this will repeatedly calling sqrt() function at every iteration wasting time and performance. Of course you can call sqrt() one time, save it into a variable and write something like this

unsigned long long square = sqrt(Number);
for (unsigned long long i = 1; i <= square; ++i)

But still we have another function call which require time. A cleaner and better way is to use i * i <= Number method.

Now I will show a final version.

Firstly we know that 0 and 1 are not primes.
Secondly, we know that every even number except 2 is not prime
Thirdly we see that it is enough if we can iterate till the square root of the number.

#include <iostream>
using namespace std;


bool IsPrime(unsigned long long Number)
{
    if (Number == 0 || Number == 1) return 0;

    else if (Number % 2 == 0 && Number != 2) return 0;

    else
    {
        for (unsigned long long i = 3; i * i <= Number; i += 2)
        {
            if (Number % i == 0) return 0;
        }
    }

    return 1;

}


int main()
{

    unsigned long long number; cout << "Enter number: "; cin >> number; cout << '\n';

    IsPrime(number) == 1 ? cout << "Prime\n" : cout << "Not prime\n";

    return 0;
}

We iterate over 2 numbers at once because we begin from 3, and if we iterate over 1 number at once, we will iterate over even numbers as well, but we already checked if our number is even at the previous step.

Observation: This algorithm is commonly used for contests and Olympics.

Another algorithm used for the primality test is the one for finding prime factors. When we have a power greater than 0, this means that we found a divisor so we can stop.

#include <iostream>
using namespace std;


bool IsPrime(unsigned long long Number)
{
    unsigned long long divisor = 2;

    while (Number > 1)
    {
        unsigned long long power = 0;

        if (Number % divisor == 0)
        {
            Number /= divisor;
            ++power;
        }

        if (power) return false;

        ++divisor;

        if (divisor * divisor > Number) return true;
    }
}


int main()
{

    unsigned long long number; cout << "Enter number: "; cin >> number; cout << '\n';

    IsPrime(number) == 1 ? cout << "Prime\n" : cout << "Not prime\n";

    return 0;
}

Time complexity here is O(sqrt(n)) in the wrost case. Because in a better case, the number is a power of divisor, for example, Number = m^k, where m = 1, 2, 3, 4,... and we perform k divisions which is O(log(n)).

Finally, we have done.

There can be many other improvements for the algorithms I showed and many others algorithms for the primality problem, but I think this is a solid introduction. Next time, I will show you another interesting algorithm called Sieve of Eratosthenes, used to find all prime numbers in a given interval. As a bonus, I will show you how this algorithm can be combined with the algorithm above to check the primality of a number. It is going to be a complex and fun algorithm.

Emanuel Rusu
You can visit my GitHub
Or you can find me on Linkedin
Next topic: Sieve of Eratosthenes
See you next time ! 👋

Simple and interesting way to convert from base 10 using recursion

Rusu Emanuel — Wed, 25 May 2022 09:02:33 +0000

👋Heeelloo everybody! 🔥🚀

As you read above, I will show you a really excellent and exciting way to convert a number from base 10 to smaller bases using the power of recursion.💪

Before we jump into the code, I will list some observations to make sure that you understand what input the program can take.

Variables are declared: unsigned long long for the input number, so you can enter any strict positive number till 2^64 - 1 and I used unsigned short for the base you can choose to convert to. You can choose between base 2 till base 10.
I focused on the idea rather than on a real-world scenario where I must consider validations and other stuff. Of course, this code can be extended to support bases up from 10 and things such as quick conversions, but I will cover these things in the future.
I have used C++ programming language.

So, what is the idea ?🤔🤔

Commonly, we repetitively divide the number by the base until the number becomes zero, then we take every rest of the divisions in reverse order, and this is the new number. This process is tough, and it requires extra variables.

Recursion does a good job here. We recursively call the same function with the new number divided until we hit the base case(the number becomes 0), then stack frames from recursion are resumed beginning from the end, so in reverse order. Now, in memory, every stack frame resulting from function calls contains a number, and the only thing we have to do is print [that number] % [the base] as the last instruction for every stack frame.

Here is the code🔥

#include <iostream>
using namespace std;


void Convert(unsigned long long Number, const unsigned short BaseToConvert)
{
    if (Number)
    {
        Convert(Number / BaseToConvert, BaseToConvert);
        cout << Number % BaseToConvert;
    }
}


int main()
{
    unsigned long long number; cout << "Number to convert: "; cin >> number;

    unsigned short baseToConvert; cout << "\nNew base: "; cin >> baseToConvert;

    cout << "\nNumber converted: "; Convert(number, baseToConvert); cout << '\n';
    return 0;
}

Thank you for reading !😃
I hope you enjoyed reading and found this interesting.

Emanuel Rusu
You can visit my GitHub
Or you can find me on Linkedin
Next topic: Algorithms for primes number - introduction
See you next time ! 👋

DEV Community: Rusu Emanuel

Binary search trees🌳

👋Heeelloo everybody! 🔥🚀

1. First step: creating a Node data type

2. Second step: generating Node variables

3. Third step: inserting nodes

4. Fourth step: printing a binary search tree

Sieve of Eratosthenes

Idea🤔

Let's take an example:

Maybe you want to see the code but let me explain it before.👨‍🏫

Observations❗:

Algorithms for primes number - introduction

Simple and interesting way to convert from base 10 using recursion

👋Heeelloo everybody! 🔥🚀

So, what is the idea ?🤔🤔

Here is the code🔥

1. First step: creating a `Node` data type

2. Second step: generating `Node` variables