1.
Problem Statement
1.1.
Constraints
1.2.
Input Format
1.3.
Output Format
2.
Sample Test Cases
3.
Approach
4.
Pseudo Code
5.
FAQs
6.
Key Takeaways
Last Updated: Mar 27, 2024

# Hidden squares

## Problem Statement

There is a golf course in the city, situated in the non-negative part of the coordinate axis (x >= 0 and y >= 0). A golfer stands at the point (0, 0), and all the other integral points contain 'the cup' (Golf hole).

The golfer can hit the ball only if the line between the golfer and the hole does not contain any other hole.

You are given a positive integer N. Find the square containing N x N points such that the golfer can't hit the ball in any of the holes in the square.

Among all the possible answers, find one with the minimum Euclidean distance of the bottom-left corner from the golfer (the origin).

As shown in the figure, the golfer can't hit the ball in the hole at coordinate (6, 2) because it is blocked by the hole at coordinate (3, 1), but the golfer can hit the ball in the hole at (3, 1) and (3, 2).

1 <= N <= 14

#### Input Format

A single integer N.

#### Output Format

In a single line, print two space-separated integers X and Y, the coordinates of the bottom left corner of the square.

Also see, Euclid GCD Algorithm

## Sample Test Cases

``````Input1 : 1
Output1 : 0 2
Explanation:
The figure shows that (0, 2) and (2, 0) are two possible answers because the distance to these points from the origin is minimum(distance = 2).
The golfer can't hit the ball to hole at (2, 2), but the euclidean distance is 4, which is not minimum, so it can't be the answer.``````

``````Input2: 2
Output2: 14 20 ``````

## Approach

Consider two points, (x1, y1) and (x2, y2), such that the golfer can hit the ball in the hole at (x1, y1), but it can't hit the ball in the hole at (x2, y2) because it is blocked by the hole at (x1, y1).

So, we can say the points (x1, y1) and (x2, y2) lie on the same line.

Also,

( x2 / g ) / ( y2 / g ) = x1 / y1

Where, g = GCD(x2, y2)

GCD(a, b) is the greatest common divisor of a and b.

So, GCD(x2, y2) > 1 and GCD(x1, y1) == 1.

By this, we can say that for every point (x, y), if the GCD(x, y) is greater than 1, then the golfer can't hit the ball in the hole at coordinate (x, y).

If maxn is the maximum value of the x-coordinate of the bottom left corner, and maxm is the maximum value of the y-coordinate.Then the most straightforward approach is to check all the coordinates (x, y) having x <= maxn and y <= maxm.

## Pseudo Code

``````maxn, maxm
N
ansX, ansY
//distance
D = INFINITY
for x, x = 1 to maxn, do
for y, y = 1 to maxm, do
isCorrect = True
for i, i = 0 to i < N, do
for j, j = 0, j < N, do
if GCD of x + i and y + j is 1
then
isCorrect = False
if isCorrect is True
then,
//compare distance
if x * x + y * y is less than D
then,
D = x * x + y * y
ansX = x
ansY = y
print ansX, print ansY``````

As N is very small (N <= 14), the time complexity of the above solution is O(maxn * maxm * log2max(maxn, maxm)).

Check out GCD Euclidean Algorithm

## FAQs

1. Why is there a Logarithmic factor in time complexity??
It is the time-complexity for calculating the GCD of two numbers.

2. How to calculate the GCD of two numbers??
In almost all the programming languages, there is a built-in function to calculate the GCD (e.g., math.gcd() in python, __gcd() in c++ 14, etc.), or we can make our own function using Extended Euclidean Algorithm.

## Key Takeaways

In this article, we solved a complex number theory problem. If you are practising competitive programming or preparing for coding interviews, then number theory is one of the most important topics. Check out this library to get a better hold on it.

To learn more about such data structures and algorithms, Coding Ninjas Studio is a one-stop destination. This platform will help you to improve your coding techniques and give you an overview of interview experiences in various product-based companies by providing Online Mock Test Series and many more benefits.

Happy learning!

Live masterclass