Recently, I encountered a problem where this relation in GCD and Fibonacci Numbers came in very handy.

Problem is, given an array of size n of positive integers and two non-negative integers l and r (0 <= l <= r < n). And we need to calculate gcd(fib(l), ...., fib(r)) where fib(i) is the ith fibonacci number.

Here, the relation that is very useful is gcd(fib(m), fib(n)) = fib(gcd(m, n)).

A more detailed description can be found here: https://www.math.hmc.edu/funfacts/ffiles/20004.5.shtml

In order to find all the divisors of a number, we have the following approaches: First is Bruteforce, where we can divide the number starting from 2 and saving those which divide completely.

vector<int> find_all_divisors(int k)
{
    vector<int> divisors;
    for(int i = 2;i < k;i++)
        if(k%i==0)
            divisors.push_back(i);
    return divisors;
}

However, the above approach takes O(n) time to complete, another approach can do this in O(√n), which iterates only till the square root of the number.

vector<int> find_all_divisors(int n)
{
    vector<int> x;
    int s = sqrt(n);
    for(int i = 1;i <= s;i++)
    {
        if (n%i==0)
        {
            if (n/i == i) // check if divisors are equal
                x.push_back(i);
            else
            {
                x.push_back(i);
                x.push_back(n/i);
            }
        }
    }
    x.push_back(n);
    return x;
}

P.S.=> Above method does not give divisors in sorted order.

Normally, a % b gives the value of remainder when a is divided by b. Therefore, 5 % 3 should give 2. But what if a is negative, in that case, the answer is multiplied by a negative sign. i.e. -5 % 3 gives -2 as answer. But what is actually is required is a positive answer.

Hence, correctly the mod function can be written as (b + (a % b)) % b.

In how many ways can you represent a number as the sum of consecutive numbers.

To solve this, we can use the concept of A.P. We know that sum of A.P. is n = (m/2)*(2*a + (m - 1)*d) if n is the sum and m is the number of integers with common difference d in the A.P. In our problem, n is the given number and m is the number of consecutive integers, obviously d is 1. Now we can derive two conclusions from above formula:

1. Manipulating the above formula as n/m = m/2 + a - 1/2 we can see that n/m is greater than m/2 becausea - 1/2 is always positive as 'a' belongs to the range [1, INF). Therefore, the conclusion is n/m > m/2 => m < sqrt(2n).

2. Above formula can also be written as a = n/m - m/2 + 1/2.From here we can conclude that n/m - m/2 + 1/2 is an integer as a is integer.

So if we iterate over m from 2 to sqrt(2n) and check for every such m that n/m - m/2 + 1/2 is integer or not. If we count the number of m's for which n/m - m/2 + 1/2 is integer then that count will be the number of ways in which we can represent n as sum of consecutive numbers.

int count = 0;
for(int i = 1;i < sqrt(2n);i++)
{
    //If n/m - m/2 + 1/2 is integer: count++
}
count is the no. of ways.

BFS

Breadth first search uses queue.If we use adjacency list to store graph then the following code will implement the BFS:

// V is the number of vertices
// s is the starting index;

list<int> G[V]; 
vector<bool> visited(V, false);
queue<int> q;

void BFS(int s)
{
    q.push_back(s);
    while(!q.empth())
    {
        s = q.front();
        cout << s << " ";
        q.pop_front();
        for(auto i = F[s].begin();i != G[s].end();i++)
        {
            if(!visited[*i])
            {
                visited[*i] = true;
                q.push_back(*i);
            }
        }
    }
}

However, this implementation will not be able to traverse a disconnected graph completely.To do so, we have to check every node by making it a starting node and BFS from that node.

for(int i = 0;i < V;i++)
{
    if(!visited[i])
        BFS(i);
}

DFS

DFS make use of stack. For than we don't have to use a separate stack, we can implement it using recursion. Following code shows implementation of DFS using assumptions taken while explaining BFS:

void DFS(int s)
{
    visited[s] = true;
    cout << s << " ";
    for(auto i = G[s].begin();i != G[s].end();i++)
        if(!visited[*i])
            DFS(*i);
}

This implementation can also be made to traverse the whole graph, in case of disconnected graph, by using the iterative calls used in BFS.

From now on I will post each and every algorithm I read and the solution to selected problems I solve on Codeforces. and other platforms.Hope the community will help me becoming a good programmer.There is also some good stuff on my other blog