# Maximize count of unique Squares that can be formed with N arbitrary points in coordinate plane

Given a positive integer **N**, the task is to find the maximum number of unique squares that can be formed with** N **arbitrary points in the coordinate plane.

**Note:** Any two squares that are not overlapping are considered unique.

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.

**Examples:**

Input:N = 9Output:5Explanation:

Consider the below square consisting of N points:The squares ABEF, BCFE, DEHG, EFIH is one of the possible squares of size 1 which are non-overlapping with each other.

The square ACIG is also one of the possible squares of size 2.

Input:N = 6Output:2

**Approach:** This problem can be solved based on the following observations:

- Observe that if
**N is a perfect square**then the maximum number of squares will be formed when**sqrt(N)*sqrt(N)**points form a grid of**sqrt(N)*sqrt(N)**and all of them are equally spaces. - But when
**N is not a perfect square**, then it still forms a grid but with the greatest number which is a perfect square having a value less than**N**. - The remaining coordinates can be placed around the edges of the grid which will lead to maximum possible squares.

Follow the below steps to solve the problem:

- Initialize a variable, say
**ans**that stores the resultant count of squares formed. - Find the maximum possible grid size as
**sqrt(N)**and the count of all possible squares formed up to length**len**to the variable**ans**which can be calculated by . - Decrement the value of
**N**by**len*len**. - If the value of
**N**is**at least len**, then all other squares can be formed by placing them in another cluster of points. Find the count of squares as calculated in**Step 2**for the value of**len**. - After completing the above steps, print the value of
**ans**as the result.

Below is the implementation of the above approach:

## C++

`// C++ program for the above approach` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Function to find the maximum number` `// of unique squares that can be formed` `// from the given N points` `int` `maximumUniqueSquares(` `int` `N)` `{` ` ` `// Stores the resultant count of` ` ` `// squares formed` ` ` `int` `ans = 0;` ` ` `// Base Case` ` ` `if` `(N < 4) {` ` ` `return` `0;` ` ` `}` ` ` `// Subtract the maximum possible` ` ` `// grid size as sqrt(N)` ` ` `int` `len = (` `sqrt` `(` `double` `(N)));` ` ` `N -= len * len;` ` ` `// Find the total squares till now` ` ` `// for the maximum grid` ` ` `for` `(` `int` `i = 1; i < len; i++) {` ` ` `// A i*i grid contains (i-1)*(i-1)` ` ` `// + (i-2)*(i-2) + ... + 1*1 squares` ` ` `ans += i * i;` ` ` `}` ` ` `// When N >= len then more squares` ` ` `// will be counted` ` ` `if` `(N >= len) {` ` ` `N -= len;` ` ` `for` `(` `int` `i = 1; i < len; i++) {` ` ` `ans += i;` ` ` `}` ` ` `}` ` ` `for` `(` `int` `i = 1; i < N; i++) {` ` ` `ans += i;` ` ` `}` ` ` `// Return total count of squares` ` ` `return` `ans;` `}` `// Driver Code` `int` `main()` `{` ` ` `int` `N = 9;` ` ` `cout << maximumUniqueSquares(N);` ` ` `return` `0;` `}` |

## Java

`// Java program for the above approach` `import` `java.io.*;` `class` `GFG {` `// Function to find the maximum number` `// of unique squares that can be formed` `// from the given N points` `static` `int` `maximumUniqueSquares(` `int` `N)` `{` ` ` `// Stores the resultant count of` ` ` `// squares formed` ` ` `int` `ans = ` `0` `;` ` ` `// Base Case` ` ` `if` `(N < ` `4` `) {` ` ` `return` `0` `;` ` ` `}` ` ` `// Subtract the maximum possible` ` ` `// grid size as sqrt(N)` ` ` `int` `len = (` `int` `)(Math.sqrt(N));` ` ` `N -= len * len;` ` ` `// Find the total squares till now` ` ` `// for the maximum grid` ` ` `for` `(` `int` `i = ` `1` `; i < len; i++) {` ` ` `// A i*i grid contains (i-1)*(i-1)` ` ` `// + (i-2)*(i-2) + ... + 1*1 squares` ` ` `ans += i * i;` ` ` `}` ` ` `// When N >= len then more squares` ` ` `// will be counted` ` ` `if` `(N >= len) {` ` ` `N -= len;` ` ` `for` `(` `int` `i = ` `1` `; i < len; i++) {` ` ` `ans += i;` ` ` `}` ` ` `}` ` ` `for` `(` `int` `i = ` `1` `; i < N; i++) {` ` ` `ans += i;` ` ` `}` ` ` `// Return total count of squares` ` ` `return` `ans;` `}` `// Driver Code` `public` `static` `void` `main (String[] args)` `{` ` ` `int` `N = ` `9` `;` ` ` `System.out.println( maximumUniqueSquares(N));` `}` `}` `// This code is contributed by shivanisinghss2110.` |

## Python3

`# Python program for the above approach` `# for math function` `import` `math` `# Function to find the maximum number` `# of unique squares that can be formed` `# from the given N points` `def` `maximumUniqueSquares(N):` ` ` ` ` `# Stores the resultant count of` ` ` `# squares formed` ` ` `ans ` `=` `0` ` ` ` ` `# Base Case` ` ` `if` `N < ` `4` `:` ` ` `return` `0` ` ` `# Subtract the maximum possible` ` ` `# grid size as sqrt(N)` ` ` `len` `=` `int` `(math.sqrt(N))` ` ` `N ` `-` `=` `len` `*` `len` ` ` `# Find the total squares till now` ` ` `# for the maximum grid` ` ` `for` `i ` `in` `range` `(` `1` `, ` `len` `):` ` ` `# A i*i grid contains (i-1)*(i-1)` ` ` `# + (i-2)*(i-2) + ... + 1*1 squares` ` ` `ans ` `+` `=` `i ` `*` `i` ` ` `# When N >= len then more squares` ` ` `# will be counted` ` ` `if` `(N >` `=` `len` `):` ` ` `N ` `-` `=` `len` ` ` `for` `i ` `in` `range` `(` `1` `, ` `len` `):` ` ` `ans ` `+` `=` `i` ` ` `for` `i ` `in` `range` `(` `1` `, N):` ` ` `ans ` `+` `=` `i` ` ` `# Return total count of squares` ` ` `return` `ans` `# Driver Code` `if` `__name__ ` `=` `=` `"__main__"` `:` ` ` `N ` `=` `9` ` ` `print` `(maximumUniqueSquares(N))` ` ` ` ` `# This code is contributed by rakeshsahni` |

## C#

`// C# program for the above approach` `using` `System;` `public` `class` `GFG` `{` ` ` `// Function to find the maximum number` ` ` `// of unique squares that can be formed` ` ` `// from the given N points` ` ` `static` `int` `maximumUniqueSquares(` `int` `N)` ` ` `{` ` ` ` ` `// Stores the resultant count of` ` ` `// squares formed` ` ` `int` `ans = 0;` ` ` ` ` `// Base Case` ` ` `if` `(N < 4) {` ` ` `return` `0;` ` ` `}` ` ` ` ` `// Subtract the maximum possible` ` ` `// grid size as sqrt(N)` ` ` `int` `len = (` `int` `)(Math.Sqrt(N));` ` ` `N -= len * len;` ` ` ` ` `// Find the total squares till now` ` ` `// for the maximum grid` ` ` `for` `(` `int` `i = 1; i < len; i++) {` ` ` ` ` `// A i*i grid contains (i-1)*(i-1)` ` ` `// + (i-2)*(i-2) + ... + 1*1 squares` ` ` `ans += i * i;` ` ` `}` ` ` ` ` `// When N >= len then more squares` ` ` `// will be counted` ` ` `if` `(N >= len) {` ` ` `N -= len;` ` ` `for` `(` `int` `i = 1; i < len; i++) {` ` ` `ans += i;` ` ` `}` ` ` `}` ` ` ` ` `for` `(` `int` `i = 1; i < N; i++) {` ` ` `ans += i;` ` ` `}` ` ` ` ` `// Return total count of squares` ` ` `return` `ans;` ` ` `}` ` ` ` ` `// Driver Code` ` ` `public` `static` `void` `Main (` `string` `[] args)` ` ` `{` ` ` `int` `N = 9;` ` ` `Console.WriteLine( maximumUniqueSquares(N));` ` ` ` ` `}` `}` `// This code is contributed by AnkThon` |

## Javascript

`<script>` `// Javascript program for the above approach` `// Function to find the maximum number` `// of unique squares that can be formed` `// from the given N points` `function` `maximumUniqueSquares(N)` `{` ` ` `// Stores the resultant count of` ` ` `// squares formed` ` ` `var` `ans = 0;` ` ` `var` `i;` ` ` `// Base Case` ` ` `if` `(N < 4) {` ` ` `return` `0;` ` ` `}` ` ` `// Subtract the maximum possible` ` ` `// grid size as sqrt(N)` ` ` `var` `len = Math.sqrt(N);` ` ` `N -= len * len;` ` ` `// Find the total squares till now` ` ` `// for the maximum grid` ` ` `for` `(i = 1; i < len; i++) {` ` ` `// A i*i grid contains (i-1)*(i-1)` ` ` `// + (i-2)*(i-2) + ... + 1*1 squares` ` ` `ans += i * i;` ` ` `}` ` ` `// When N >= len then more squares` ` ` `// will be counted` ` ` `if` `(N >= len) {` ` ` `N -= len;` ` ` `for` `(i = 1; i < len; i++) {` ` ` `ans += i;` ` ` `}` ` ` `}` ` ` `for` `(i = 1; i < N; i++) {` ` ` `ans += i;` ` ` `}` ` ` `// Return total count of squares` ` ` `return` `ans;` `}` `// Driver Code` ` ` `var` `N = 9;` ` ` `document.write(maximumUniqueSquares(N));` `// This code is contributed by SURENDRA_GANGWAR.` `</script>` |

**Output:**

5

**Time Complexity:** O(sqrt(N)) **Auxiliary Space:** O(1)