Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

rootn's blog

By rootn, history, 11 months ago, ,

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

• +46

By rootn, 14 months ago, ,

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.

• -18

By rootn, history, 2 years ago, ,

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.

• -1

By rootn, history, 3 years ago, ,

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 = 2;i < sqrt(2n);i++)
{
//If n/m - m/2 + 1/2 is integer: count++
}
count is the no. of ways.


• +16

By rootn, history, 3 years ago, ,

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.

• +6

By rootn, history, 3 years ago, ,

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