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

Question

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

Comments

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

Answer 1

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;
}