CodeFights - Count Black Cells - Solution

Problem

Imagine a white rectangular grid of n rows and m columns divided into two parts by a diagonal line running from the upper left to the lower right corner. Now let's paint the grid in two colors according to the following rules:
  • A cell is painted black if it has at least one point in common with the diagonal;
  • Otherwise, a cell is painted white.
Count the number of cells painted black.

Solution

Here is the code that solves the problem:
 
int gcd(int n, int m){
    while (m) {
        int temp = n;
        n = m;
        m = temp%m;
    }
    
    return n;
}
int countBlackCells(int n, int m) {
    if (n == m) return (n + 2*(n-1));
    if (n == 1 or m==1 ) return n*m;
    return n + m -gcd(n, m) + (gcd(n, m)-1)*2;
}


1 comment:

  1. I'm truly enjoying the design and layout of your site. It's a very easy on the eyes which makes it much more pleasant for me to come here and visit more often. Did you hire out a designer to create your theme? Superb work! Software de Activos Fijos

    ReplyDelete