Hidden squares

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!