Given a number N, the task is to find the integer points (x, y) such that 0 <= x, y <= N and Manhattan distance between any two points will be atleast N.
Examples:
Input: N = 3 Output: (0, 0) (0, 3) (3, 0) (3, 3) Input: N = 4 Output: (0, 0) (0, 4) (4, 0) (4, 4) (2, 2)
Approach:
- Manhattan Distance between two points (x1, y1) and (x2, y2) is:
|x1 – x2| + |y1 – y2| - Here for all pair of points this distance will be atleast N.
- As 0 <= x <= N and 0 <= y <= N so we can imagine a square of side length N whose bottom left corner is (0, 0) and top right corner is (N, N).
- So if we place 4 points in this corner then Manhattan distance will be atleast N.
- Now as we have to maximize the number of the point we have to check is there any available point inside the square.
- If N is even then middle point of the square which is (N/2, N/2) is integer point, otherwise, it will be float value as N/2 is not a integer when N is odd.
- So the only available position is the middle point and we can put a point there only if N is even.
- So number of points will be 4 if N is odd and if N is even then the number of points will be 5.
Below is the implementation of the above approach:
C++
// C++ code to Find the integer points (x, y)// with Manhattan distance atleast N#include <bits/stdc++.h>using namespace std;// C++ function to find all possible pointvector<pair<int, int> > FindPoints(int n){ vector<pair<int, int> > v; // Find all 4 corners of the square // whose side length is n v.push_back({ 0, 0 }); v.push_back({ 0, n }); v.push_back({ n, 0 }); v.push_back({ n, n }); // If n is even then the middle point // of the square will be an integer, // so we will take that point if (n % 2 == 0) v.push_back({ n / 2, n / 2 }); return v;}// Driver Codeint main(){ int N = 8; vector<pair<int, int> > v = FindPoints(N); // Printing all possible points for (auto i : v) { cout << "(" << i.first << ", " << i.second << ") "; } return 0;} |
Java
// Java code to Find the integer points (x, y)// with Manhattan distance atleast Nimport java.util.*;class GFG{static class pair{ int first, second; public pair(int first, int second) { this.first = first; this.second = second; } }// Java function to find all possible pointstatic Vector<pair> FindPoints(int n){ Vector<pair> v = new Vector<pair>(); // Find all 4 corners of the square // whose side length is n v.add(new pair( 0, 0 )); v.add(new pair( 0, n )); v.add(new pair( n, 0 )); v.add(new pair( n, n )); // If n is even then the middle point // of the square will be an integer, // so we will take that point if (n % 2 == 0) v.add(new pair( n / 2, n / 2 )); return v;}// Driver Codepublic static void main(String[] args){ int N = 8; Vector<pair > v = FindPoints(N); // Printing all possible points for (pair i : v) { System.out.print("(" + i.first + ", " + i.second + ") "); }}}// This code is contributed by PrinciRaj1992 |
Python3
# Python3 code to Find the integer points (x, y) # with Manhattan distance atleast N # function to find all possible point def FindPoints(n) : v = []; # Find all 4 corners of the square # whose side length is n v.append([ 0, 0 ]); v.append([ 0, n ]); v.append([ n, 0 ]); v.append([ n, n ]); # If n is even then the middle point # of the square will be an integer, # so we will take that point if (n % 2 == 0) : v.append([ n // 2, n // 2 ]); return v; # Driver Code if __name__ == "__main__" : N = 8; v = FindPoints(N); # Printing all possible points for element in v : print("(", element[0], ",", element[1], ")", end = " "); # This code is contributed by AnkitRai01 |
C#
// C# code to Find the integer points (x, y)// with Manhattan distance atleast Nusing System;using System.Collections.Generic;class GFG{class pair{ public int first, second; public pair(int first, int second) { this.first = first; this.second = second; } }// Function to find all possible pointstatic List<pair> FindPoints(int n){ List<pair> v = new List<pair>(); // Find all 4 corners of the square // whose side length is n v.Add(new pair( 0, 0 )); v.Add(new pair( 0, n )); v.Add(new pair( n, 0 )); v.Add(new pair( n, n )); // If n is even then the middle point // of the square will be an integer, // so we will take that point if (n % 2 == 0) v.Add(new pair( n / 2, n / 2 )); return v;}// Driver Codepublic static void Main(String[] args){ int N = 8; List<pair > v = FindPoints(N); // Printing all possible points foreach (pair i in v) { Console.Write("(" + i.first + ", " + i.second + ") "); }}}// This code is contributed by Rajput-Ji |
Javascript
<script>// Javascript code to Find the integer points (x, y)// with Manhattan distance atleast N// C++ function to find all possible pointfunction FindPoints(n){ var v = []; // Find all 4 corners of the square // whose side length is n v.push([ 0, 0 ]); v.push([ 0, n ]); v.push([ n, 0 ]); v.push([ n, n ]); // If n is even then the middle point // of the square will be an integer, // so we will take that point if (n % 2 == 0) v.push([ n / 2, n / 2 ]); return v;}// Driver Codevar N = 8;var v = FindPoints(N);// Printing all possible pointsv.forEach(i => { document.write( "(" + i[0] + ", " + i[1] + ") ");});// This code is contributed by rrrtnx.</script> |
Output:
(0, 0) (0, 8) (8, 0) (8, 8) (4, 4)
Time Complexity: O(1)
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!
