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

0 0 5 minutes read

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.

Examples:

Input: N = 9
Output: 5
Explanation:
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 = 6
Output: 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 $\sum_{i = 1}^{i = len} i*i$ .
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:

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

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!