Basic Operators

Today we will be talking about operations. There are many different types of operations :

• & - You can use it to check if a number is divisible by 2.
• ^ - This is the XOR operator. XOR has property : the same number XOR the same number equal to zero.
• 2 power n can be done in constant time with bit operation <<. Ex. (1<<n)
• Multiplication and division are slower then bit operations. (n >>= 1) is equivalent as n /= 2.     (n <<= 1) is equivalent as n *= 2.
• the or bit operation
• n++ - increment n by 1
• n-- - subtracts n by 1
• ++n - increment n by 1
• --n - subtracts n by 1
• n%m = r - r is the remainder of the division n and m
• *, -,  /, + - basic arithmetic operators

Fibonacci Numbers

One famous question about Fibonacci numbers is about rabbits. Say rabbits are able to mate at the age of one month, and pregnancy takes one month. Thus, at the end of its second month, a female can produce another pair of rabbits. Rabbits never die, and a mating pair always produces one new pair (one male, one female) every month from the second month on. The puzzle that Fibonacci posed was if we start with a new pair from birth, how many pairs will there be in one year ?

To solve this problem we are using the following formula : f(n-1)+f(n-2)=f(n). This can be done in recursive and iterative. I prefer the iterative version because in iterative we can do in O(1) memory and O(n) time.

Here is the C++ code to calcute the fibonnacci numbers to the nth term:

int prev1=1,prev2=1;

for (int i=2; i<n; ++i){

   swap(prev1,prev2);

   prev2=prev1+prev2;

}

cout << prev2;

Another way to calculate Fibonnacci number. If Fn is the nth Fibonacci number then :

This is Binet's formula

Distances

There are many different distances but today we will be talking about Manhattan distance and Euclidean distance. Mahattan distance is based on the gridlike street geography of the New York borough of Mahattan.
For 2D : Manhattan Distance's formula is abs(x1-x2)+abs(y1-y2). Euclidean distance's formula is sqrt((x1-x2)^2+(y1-y2)^2). This is equivalent to the Pythagorean theorem.
This chapter is an easy, short and fundamental chapter. (in fact the whole math chapter is easy, short and fundamental)

In the picture, in red, blue and yellow, you have Manhattan distance. And in green is the Euclidean distance.

Big Number Addition

This is a very basic problem : Given two numbers up to 1 million, N and M.
And given N digits representing the first number. Then another M digits representing the second number.

ex :

INPUT

4 5
1 2 3 4
5 4 3 2 1

OUTPUT

66661

If you use Python then it is a very very very easy problem because Python supports numbers in a infinity of digits. But if you are a Java, C++ programmer then you can't do it like simple two number addition. So to do that, you just need to know how to addition big numbers at primary school. So you do :

remainder : nothing
                   1112
                  +  34
                  -------
                   1146

So now I think you can implement it yourself (each time do addition then modulo 10), if anyone needs a C++ code, you can ask me.

Prime numbers

Prime numbers are numbers that can only be divided by itself and one. A prime number has two divisors so one is not a prime number. Prime numbers have been proved that there are a infinity of them by Euclid in Euclid's Element. Two numbers are said to be coprime if the only divisor that divides both of them is one (gcd(a,b) = 1). Here, we are going to tell you different ways to check if a number is a prime number. One technique is to do a brute force algorithm, this algorithm will see if there is a number from 2 to n-1 that can divide n.

Brute force

Pseudo-code :

for i=2 to i=n-1 i += 1 {
    if n % i == 0 {
        print : n is composite
        break
    }
}

C++ code :

for (int i=2; i<=n-1; ++i){
    if (n%i == 0){
        cout << n " is composite\n";
        break;
    }
}

Optimisation : you might have already seen that n can not be divided by sqrt(n)+1 so in the above for loop you could replace n-1 and put sqrt(n). This algorithm can be inefficient if we have two thousand integers to check.

Sieve of Eratosthenes

This solution consists to take the next  number let's say n that has not been marked as true and every number that have n as divisor and have not been marked are marked as true.

Pseudo-code for finding prime numbers from 2 to 100000 :

for i=2 to i=100000 i += 1 {
    if not vu[i] {
        for j=2*i to j=100000 j += i vu[j]=true;
    }
}
// all numbers where vu[i] = false are prime numbers

C++ code for finding prime numbers from 2 to 100000 :

for (int i=2; i<100001; ++i){
    if (!vu[i]){
        for (int j=2*i; j<100001; ++j) vu[j]=true;
    }
}
// all numbers where vu[i] = false are prime numbers

Optimisation : In the first loop, we can see that we only need to do the loop to sqrt(100000) or sqrt(n). In this case n=100000. Also it is possible to do this algorithm in O(n).

Different Integer

In C++, you have a huge amount of varieties of numbers. When you add unsigned in front of a type like int (except : bool, char) then the type will no longer support negative numbers.

• Bool  0 or 1
• Char  0 to 9
• Short  - 2^16 to 2^16
• Int (32 bits) -2^32 to 2^32
• Long or long long -2^63 to 2^63
• Unsigned long long 0 to 2^64

You also have complex numbers in C++ if you include the following line : #include <complex>
When you have included that line, you can :

• initialise a complex table like this : complex<double> mycomplex(10.0,0.01);
• print the real part with real()
• print the imaginary part with imag()
• print the phase angle of a complex number with arg()
• print the complex projection with proj()
• print the complex conjugate with conj()
• print the norm of a complex  number with norm()
• print absolute value of a complex number with abs()
• ......

GCD and LCM

GCD also called Greatest Commun Divisor is a basic algorithm created by Euclid (Mid 4th century BC - Mid 3rd century BC). LCM also called Lowest Commun Multiple is a basic algorithm also created bu Euclid and it's formula depends on GCD. Here's the formula : a*b/GCD(a,b).
Theoreme (Euclide's lemma) : Consider A and B two integers; if R is the rest of the euclideen division of A and B then GCD(A,B)=GCD(B,R).

Pseudo-code

GCD can be implemented in two different ways : recursive and iterative. I recommand the recursive solution because it is shorter.

GCD(a,b) {
    if b == 0 return a
    return GCD(b,a%b)
}

GCD(a,b) {
   while a != b {
      if a > b a -= b;
      else b -= a;
   }
   return a;
}

C++ code

In C++ there is a gcd() function and a lcm function (for those who are tired to do a multiplication and a division) in numeric. There is also a new gcd function but it requires C++17, it is called __gcd().

#include <iostream>
#include <numeric>
#include <algorithm>
using namespace std;

inline int GCD_1(int a, int b){
 if (b == 0) return a;
 return GCD_1(b,a%b);
}

inline int GCD_2(int a, int b){
 while (a != b){
  if (a > b) a -= b;
  else b -= a;
 }
 return a;
}

inline int GCD_3(int a, int b){
 return gcd(a,b);
}

int main(){
 ios::sync_with_stdio(0);
 cin.tie(0);
 int a,b;
 cin >> a >> b;
 cout << "GCD 1,2,3 result : " << GCD_1(a,b);
 cout << ' ' << GCD_2(a,b) << ' ' << GCD_3(a,b) << '\n';
 cout << "LCM result : ";
        cout << a*b/GCD_1(a,b) << ' ' << lcm(a,b) << '\n';
 return 0;
}

Another technique is to use tie :

//Greatest common divisor, the way Euclid intended :

int gcd(int a, int b){

    while (b != 0){

        tie(a,b) = make_tuple(b , a%b);

    }

    return a;

}

Math - Course 2

Math is a subject that everyone has learned at school so this chapter should be a bit easier for everyone to understand. This chapter will contain all the fundemental or easier knowledge. We will provide a more advanced chapter on math in the future. In this course we will provide one article per day (if possible). Also in Big Number Addition, we will also provide code and explanations for Big Number Substraction.

Start : Saturday 2nd March 2019

End (likely) : Wednesday 13th March 2019

Here are the main subjects :

1. GCD and LCM
2. Distances
3. Different Integer
4. Prime Numbers
5. Fibonacci Numbers
6. Venn Diagram
7. Base
8. Bitset
9. Factorials
10. Basic operators
11. Triangles
12. Permutations
13. Cmath Library
14. Big Number Addition