Given an array points[] representing N points in a K-dimensional space, the task is to find the count of pairs of points in the space such that the distance between the points of each pair is an integer value.
Examples:
Input: points[] = { {1, 2}, {5, 5}, {2, 8} }, K = 2
Output: 1
Explanation:
Distance between points of the pair(points[0], points[1]) = 5
Distance between points of the pair(points[1], points[2]) = sqrt(58)
Distance between points of the pair(points[0], points[2]) = 3 * sqrt(5)
Therefore, the required output is 1.Input: points[] = { {-3, 7, 8, 2}, {-12, 1, 10, 2}, {-2, 8, 9, 3} }, K = 4
Output: 2.
Approach: The idea is to generate all possible pairs of the given array and find the distance between the points of each pair and check if it is an integer value or not. If found to be true, then increment the count. Finally, print the total count obtained. Follow the steps below to solve the problem:
- Distance between the points of the pair({ a1, a2, …, aK }, { b1, b2, …, bK }) can be calculated using the below formula:
Distance(a, b) = sqrt(((a1 – b1)2 + (a2 – b2)2 + …. + (aK – bK)2 ))
- Traverse the array, and generate all possible pairs of the given array.
- For each pair of points, check if the distance between the points of the pair is an integer or not. If found to be true, then increment the count.
- Finally, print the count obtained.
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 pairs whose distance between// the points of is an integer value.void cntPairs(vector<vector<int> > points, int n, int K){ // Stores count of pairs whose distance // between points is an integer int ans = 0; // Traverse the array, points[] for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { // Stores distance between // points(i, j) int dist = 0; // Traverse all the points of // current pair for (int k = 0; k < K; k++) { // Update temp int temp = (points[i][k] - points[j][k]); // Update dist dist += temp * temp; } // If dist is a perfect square if (sqrt(dist) * sqrt(dist) == dist) { // Update ans ans += 1; } } } cout << ans << endl;}// Driver Codeint main(){ // Given value of K int K = 2; // Given points vector<vector<int> > points = { { 1, 2 }, { 5, 5 }, { -2, 8 } }; // Given value of N int n = points.size(); // Function Call cntPairs(points, n, K); return 0;} |
Java
// Java program for the above approachclass GFG{ // Function to find pairs whose distance between // the points of is an integer value. static void cntPairs(int [][]points, int n, int K) { // Stores count of pairs whose distance // between points is an integer int ans = 0; // Traverse the array, points[] for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { // Stores distance between // points(i, j) int dist = 0; // Traverse all the points of // current pair for (int k = 0; k < K; k++) { // Update temp int temp = (points[i][k] - points[j][k]); // Update dist dist += temp * temp; } // If dist is a perfect square if (Math.sqrt(dist) * Math.sqrt(dist) == dist) { // Update ans ans += 1; } } } System.out.print(ans +"\n"); } // Driver Code public static void main(String[] args) { // Given value of K int K = 2; // Given points int [][]points = { { 1, 2 }, { 5, 5 }, { -2, 8 } }; // Given value of N int n = points.length; // Function Call cntPairs(points, n, K); }}// This code is contributed by shikhasingrajput |
Python3
# Python program for the above approach# Function to find pairs whose distance between# the points of is an integer value.def cntPairs(points, n, K): # Stores count of pairs whose distance # between points is an integer ans = 0 # Traverse the array, points[] for i in range(0, n): for j in range(i + 1, n): # Stores distance between # points(i, j) dist = 0 # Traverse all the points of # current pair for k in range(K): # Update temp temp = (points[i][k] - points[j][k]) # Update dist dist += temp * temp # If dist is a perfect square if (((dist)**(1/2)) * ((dist)**(1/2)) == dist): # Update ans ans += 1 print(ans)# Driver Code# Given value of KK = 2# Given pointspoints = [ [ 1, 2 ], [ 5, 5 ], [ -2, 8 ]]# Given value of Nn = len(points)# Function CallcntPairs(points, n, K)# This code is contributed by rohitsingh07052. |
C#
// C# program for the above approachusing System;class GFG{ // Function to find pairs whose distance between // the points of is an integer value. static void cntPairs(int[, ] points, int n, int K) { // Stores count of pairs whose distance // between points is an integer int ans = 0; // Traverse the array, points[] for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { // Stores distance between // points(i, j) int dist = 0; // Traverse all the points of // current pair for (int k = 0; k < K; k++) { // Update temp int temp = (points[i, k] - points[j, k]); // Update dist dist += temp * temp; } // If dist is a perfect square if (Math.Sqrt(dist) * Math.Sqrt(dist) == dist) { // Update ans ans += 1; } } } Console.WriteLine(ans); } // Driver Code public static void Main() { // Given value of K int K = 2; // Given points int[, ] points = { { 1, 2 }, { 5, 5 }, { -2, 8 } }; // Given value of N int n = points.GetLength(0); // Function Call cntPairs(points, n, K); }}// This code is contributed by chitranayal. |
Javascript
<script>// javascript program for the above approach // Function to find pairs whose distance between // the points of is an integer value. function cntPairs(points , n , K) { // Stores count of pairs whose distance // between points is an integer var ans = 0; // Traverse the array, points for (i = 0; i < n; i++) { for (j = i + 1; j < n; j++) { // Stores distance between // points(i, j) var dist = 0; // Traverse all the points of // current pair for (k = 0; k < K; k++) { // Update temp var temp = (points[i][k] - points[j][k]); // Update dist dist += temp * temp; } // If dist is a perfect square if (Math.sqrt(dist) * Math.sqrt(dist) == dist) { // Update ans ans += 1; } } } document.write(ans + "\n"); } // Driver Code // Given value of K var K = 2; // Given points var points = [ [ 1, 2 ], [ 5, 5 ], [ -2, 8 ] ]; // Given value of N var n = points.length; // Function Call cntPairs(points, n, K);// This code contributed by Rajput-Ji</script> |
Output:
1
Time Complexity: O(N2 * K)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
