Hackerrank Solution: Circle City

Original Problem

Roy lives in a city that is circular in shape on a 2D plane that has radius \(r\). The city center is located at origin \((0, 0)\) and it has suburbs lying on the lattice points (points with integer coordinates). The city Police Department Headquarters can only protect those suburbs which are located strictly inside the city. The suburbs located on the border of the city are still unprotected. So the police department decides to build at most \(k\) additional police stations at some suburbs. Each of these police stations can protect the suburb it is located in.

Given the square of radius \(d=r^2\), of the city, Roy has to determine if it is possible to protect all the suburbs.

Input Format

The first line of input contains integer \(t\); \(t\) test cases follow. Each of the next \(t\) lines contains two space-separated integers: \(d\) , the square of the radius of the city, and \(k\), the maximum number of police stations the headquarters is willing to build.

Constraints

• \(1\leq t\leq 10^3\)
• \(1\leq d\leq 2\times 10^9\)
• \(0\leq k\leq 2\times 10^9\)

Output Format

For each test case, print in a new line possible if it is possible to protect all the suburbs;, otherwise, print impossible.

Sample Input

5
1 3
1 4
4 4
25 11
25 12

Sample Output

impossible
possible
possible
impossible
possible

Solution

We have given the circle with radius \(r\) and origin \((0, 0)\). Finding the number of points on the circumference with integer coordinates is one of the classical lattice point problems. To find all lattice points, we need to find all \((x, y)\) that satisfy

\[x^2+y^2=r^2=d\]

When we loop from \(x:=1\) to \(r\) and check if \(d-x^2=y^2\) is a perfect square, we have found one lattice point. Since we do this for one quadrant only, we have to multiply the resulting number of points by 4. The straightforward implementation is then:

function solve(d, k) {
  let c = 0;
  for (let x = 1; x*x <= d; x++) {
    if (isPerfectSquare(d - x * x))
      c+= 4;
  }
  return c <= k ? "possible" : "impossible";
}

using our optimized implementation of isPerfectSquare , we derived in Determining if a number is a perfect square:

function isPerfectSquare(n) {
  let r = n & 15;
  if (r == 0 || r == 1 || r == 4 || r == 9) {
    for (let i = 0; i * i <= n; i++) { 

      if (i * i === n) { 
        return true; 
      } 
    }
  }
  return false; 
}