<Codesignal> Count Black Cells

Medium

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.

Example

• For n = 3 and m = 4, the output should be
  countBlackCells(n, m) = 6.

  There are 6 cells that have at least one common point with the diagonal and therefore are painted black.

  

• For n = 3 and m = 3, the output should be
  countBlackCells(n, m) = 7.

  7 cells have at least one common point with the diagonal and are painted black.

  

Input/Output

• [execution time limit] 0.5 seconds (c)

• [input] integer n

  The number of rows.

  Guaranteed constraints:
  1 ≤ n ≤ 10^5.

• [input] integer m

  The number of columns.

  Guaranteed constraints:
  1 ≤ m ≤ 10^5.

• [output] integer

  • The number of black cells.

[C] Syntax Tips

// Prints help message to the console
// Returns a string
char * helloWorld(char * name) {
    char * answer = malloc(strlen(name) + 8);
    printf("This prints to the console when you Run Tests");
    strcpy(answer, "Hello, ");
    strcat(answer, name);
    return answer;
}

---

Solution

int gcd(int x,int y)
{
	if(x<y)
	{
		int temp=x;
		x=y;
		y=temp;
	}

	while(y>0)
	{
		int temp=x%y;
		x=y;
		y=temp;
	}

	return x;
}

int countBlackCells(int n,int m)
{
	return n+m+gcd(n,m)-2;
}