Given two arrays X[] and Y[] consisting of N and M integers such that there are N lines parallel to the y-axis and M lines parallel to the x-axis. The task is to find the total number of squares formed by these lines on a coordinate plane.
Each integer(say a) in the array X[] denotes lines having equation x = a, parallel to y-axis.
Each integer(say b) in the array Y[] denotes lines having equation y = b, parallel to x-axis.
Examples:
Input: N = 3, M = 4, X[] = {1, 3, 7}, Y[] = {2, 4, 6, 1}
Output: 3
Explanation:
3 lines are parallel to y-axis for x = 1, x = 3 and x = 7.
4 lines are parallel to x-axis for y = 2, y = 4, y = 6 and y = 1.
From the above image, below are three possible squares formed:
1) square CDEF (x = 1, x = 3, y = 2, y = 4), side = 2 units.
2) square ABDC (x = 1, x = 3, y = 4, y = 6), side = 2 units.
3) square BGHF (x = 3, x = 7, y = 2, y = 6), side = 4 units.Input: N = 5, M = 4, X[] = {1, 9, 2, 3, 7}, Y[] = {1, 2, 4, 6}
Output: 8
Approach: Follow the steps below to solve the problem:
- Find the distance between all pairs in X[] array and store the count in a Map, say M1.
- Find the distance between all pairs in Y[] array and store the count in a Map M2.
- If the distance of pairs of M1 is present in M2, then a square can be made by using both the pairs.
- Therefore, the total count of squares can be calculated by adding all the counts of distances stored in M1 as well as in M2.
- Print the total count of squares after completing the above steps.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to count all the possible// squares with given lines parallel// to both the X and Y axisint numberOfSquares(int X[], int Y[], int N, int M){ // Stores the count of all possible // distances in X[] & Y[] respectively unordered_map<int, int> m1, m2; int i, j, ans = 0; // Find distance between all // pairs in the array X[] for (i = 0; i < N; i++) { for (j = i + 1; j < N; j++) { int dist = abs(X[i] - X[j]); // Add the count to m1 m1[dist]++; } } // Find distance between all // pairs in the array Y[] for (i = 0; i < M; i++) { for (j = i + 1; j < M; j++) { int dist = abs(Y[i] - Y[j]); // Add the count to m2 m2[dist]++; } } // Find sum of m1[i] * m2[i] // for same distance for (auto i = m1.begin(); i != m1.end(); i++) { // Find current count in m2 if (m2.find(i->first) != m2.end()) { // Add to the total count ans += (i->second * m2[i->first]); } } // Return the final count return ans;}// Driver Codeint main(){ // Given lines int X[] = { 1, 3, 7 }; int Y[] = { 2, 4, 6, 1 }; int N = sizeof(X) / sizeof(X[0]); int M = sizeof(Y) / sizeof(Y[0]); // Function Call cout << numberOfSquares(X, Y, N, M); return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.util.*;class GFG{// Function to count all the possible// squares with given lines parallel// to both the X and Y axisstatic int numberOfSquares(int[] X, int[] Y, int N, int M){ // Stores the count of all possible // distances in X[] & Y[] respectively HashMap<Integer, Integer> m1 = new HashMap<Integer, Integer>(); HashMap<Integer, Integer> m2 = new HashMap<Integer, Integer>(); int i, j, ans = 0; // Find distance between all // pairs in the array X[] for(i = 0; i < N; i++) { for(j = i + 1; j < N; j++) { int dist = Math.abs(X[i] - X[j]); // Add the count to m1 m1.put(dist, m1.getOrDefault(dist, 0) + 1); } } // Find distance between all // pairs in the array Y[] for(i = 0; i < M; i++) { for(j = i + 1; j < M; j++) { int dist = Math.abs(Y[i] - Y[j]); // Add the count to m2 m2.put(dist, m2.getOrDefault(dist, 0) + 1); } } // Find sum of m1[i] * m2[i] // for same distance for(Map.Entry<Integer, Integer> entry : m1.entrySet()) { // Find current count in m2 if (m2.containsKey(entry.getKey())) { // Add to the total count ans += (entry.getValue() * m2.get(entry.getKey())); } } // Return the final count return ans;}// Driver Codepublic static void main(String[] args){ // Given lines int X[] = { 1, 3, 7 }; int Y[] = { 2, 4, 6, 1 }; int N = X.length; int M = Y.length; // Function call System.out.println(numberOfSquares(X, Y, N, M));}}// This code is contributed by akhilsaini |
Python3
# Python3 program for the above approach# Function to count all the possible# squares with given lines parallel# to both the X and Y axisdef numberOfSquares(X, Y, N, M): # Stores the count of all possible # distances in X[] & Y[] respectively m1 = {} m2 = {} ans = 0 # Find distance between all # pairs in the array X[] for i in range(0, N): for j in range(i + 1, N): dist = abs(X[i] - X[j]) # Add the count to m1 if dist in m1: m1[dist] = m1[dist] + 1 else: m1[dist] = 1 # Find distance between all # pairs in the array Y[] for i in range(0, M): for j in range(i + 1, M): dist = abs(Y[i] - Y[j]) # Add the count to m2 if dist in m2: m2[dist] = m2[dist] + 1 else: m2[dist] = 1 # Find sum of m1[i] * m2[i] # for same distance for key in m1: # Find current count in m2 if key in m2: # Add to the total count ans = ans + (m1[key] * m2[key]) # Return the final count return ans# Driver Codeif __name__ == "__main__": # Given lines X = [ 1, 3, 7 ] Y = [ 2, 4, 6, 1 ] N = len(X) M = len(Y) # Function call print(numberOfSquares(X, Y, N, M))# This code is contributed by akhilsaini |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{// Function to count all the possible// squares with given lines parallel// to both the X and Y axisstatic int numberOfSquares(int[] X, int[] Y, int N, int M){ // Stores the count of all possible // distances in X[] & Y[] respectively Dictionary<int, int> m1 = new Dictionary<int, int>(); Dictionary<int, int> m2 = new Dictionary<int, int>(); int i, j, ans = 0; // Find distance between all // pairs in the array X[] for(i = 0; i < N; i++) { for(j = i + 1; j < N; j++) { int dist = Math.Abs(X[i] - X[j]); // Add the count to m1 if (m1.ContainsKey(dist)) m1[dist]++; else m1.Add(dist, 1); } } // Find distance between all // pairs in the array Y[] for(i = 0; i < M; i++) { for(j = i + 1; j < M; j++) { int dist = Math.Abs(Y[i] - Y[j]); // Add the count to m2 if (m2.ContainsKey(dist)) m2[dist]++; else m2.Add(dist, 1); } } // Find sum of m1[i] * m2[i] // for same distance foreach(KeyValuePair<int, int> entry in m1) { // Find current count in m2 if (m2.ContainsKey(entry.Key)) { // Add to the total count ans += (entry.Value * m2[entry.Key]); } } // Return the final count return ans;}// Driver Codepublic static void Main(){ // Given lines int[] X = { 1, 3, 7 }; int[] Y = { 2, 4, 6, 1 }; int N = X.Length; int M = Y.Length; // Function call Console.WriteLine(numberOfSquares(X, Y, N, M));}}// This code is contributed by akhilsaini |
Javascript
<script>// Javascript program for the above approach// Function to count all the possible// squares with given lines parallel// to both the X and Y axisfunction numberOfSquares(X, Y, N, M){ // Stores the count of all possible // distances in X[] & Y[] respectively var m1 = new Map(), m2 = new Map(); var i, j, ans = 0; // Find distance between all // pairs in the array X[] for (i = 0; i < N; i++) { for (j = i + 1; j < N; j++) { var dist = Math.abs(X[i] - X[j]); // Add the count to m1 if(m1.has(dist)) m1.set(dist, m1.get(dist)+1) else m1.set(dist, 1); } } // Find distance between all // pairs in the array Y[] for (i = 0; i < M; i++) { for (j = i + 1; j < M; j++) { var dist = Math.abs(Y[i] - Y[j]); // Add the count to m2 if(m2.has(dist)) m2.set(dist, m2.get(dist)+1) else m2.set(dist, 1); } } // Find sum of m1[i] * m2[i] // for same distance m1.forEach((value, key) => { // Find current count in m2 if (m2.has(key)) { // Add to the total count ans += (value * m2.get(key)); } }); // Return the final count return ans;}// Driver Code// Given linesvar X = [1, 3, 7];var Y = [2, 4, 6, 1];var N = X.length;var M = Y.length;// Function Calldocument.write( numberOfSquares(X, Y, N, M));// This code is contributed by rrrtnx.</script> |
Output:
3
Time Complexity: O(M2+ N2)
Auxiliary Space: O(M2+ N2)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
