# How to count number of squares on a chessboard type n*n board using a C program?

138 views

Say you are given a 2X2 board then number of squares are 5. Can someone help with the logic and sample program?

posted Mar 13, 2016

I think its pretty straight forward, logic is -
1^2+2^2+...+n^2

Below is C++ implementation of above formula. Since the value of n*(n+1)*(2n+1) can cause overflow for large values of n, below are some interesting tricks used in the program.
1) long int is used in return.
2) n * (n + 1) / 2 is evaluated first as the value n*(n+1) will always be a multiple of 2.
Note that overflow may still happen, but above tricks just reduce chances of overflow.

``````#include <iostream>
using namespace std;

// Function to return count of squares;
long int countSquares(int n)
{
// A better way to write n*(n+1)*(2n+1)/6
return (n * (n + 1) / 2) * (2*n + 1) / 3;
}

int main()
{
int n = 4;
cout << "Count of squares is " << countSquares(n);
return 0;
}
``````
answer Mar 13, 2016
Similar Questions