Circle and Lattice Points
Given a circle of radius r in 2-D with origin or (0, 0) as center. The task is to find the total lattice points on circumference. Lattice Points are points with coordinates as integers in 2-D space.
Example:
Input : r = 5.
Output : 12
Below are lattice points on a circle with
radius 5 and origin as (0, 0).
(0,5), (0,-5), (5,0), (-5,0),
(3,4), (-3,4), (-3,-4), (3,-4),
(4,3), (-4,3), (-4,-3), (4,-3).
are 12 lattice point.
To find lattice points, we basically need to find values of (x, y) which satisfy the equation x2 + y2 = r2.
For any value of (x, y) that satisfies the above equation we actually have total 4 different combination which that satisfy the equation. For example if r = 5 and (3, 4) is a pair which satisfies the equation, there are actually 4 combinations (3, 4) , (-3,4) , (-3,-4) , (3,-4). There is an exception though, in case of (0, r) or (r, 0) there are actually 2 points as there is no negative 0.
// Initialize result as 4 for (r, 0), (-r. 0),
// (0, r) and (0, -r)
result = 4
Loop for x = 1 to r-1 and do following for every x.
If r*r - x*x is a perfect square, then add 4
tor result.
Below is the implementation of above idea.
// C++ program to find countLattice points on a circle
#include<bits/stdc++.h>
using namespace std;
// Function to count Lattice points on a circle
int countLattice(int r)
{
if (r <= 0)
return 0;
// Initialize result as 4 for (r, 0), (-r. 0),
// (0, r) and (0, -r)
int result = 4;
// Check every value that can be potential x
for (int x=1; x<r; x++)
{
// Find a potential y
int ySquare = r*r - x*x;
int y = sqrt(ySquare);
// checking whether square root is an integer
// or not. Count increments by 4 for four
// different quadrant values
if (y*y == ySquare)
result += 4;
}
return result;
}
// Driver program
int main()
{
int r = 5;
cout << countLattice(r);
return 0;
}
// Java program to find
// countLattice points on a circle
class GFG
{
// Function to count
// Lattice points on a circle
static int countLattice(int r)
{
if (r <= 0)
return 0;
// Initialize result as 4 for (r, 0), (-r. 0),
// (0, r) and (0, -r)
int result = 4;
// Check every value that can be potential x
for (int x=1; x<r; x++)
{
// Find a potential y
int ySquare = r*r - x*x;
int y = (int)Math.sqrt(ySquare);
// checking whether square root is an integer
// or not. Count increments by 4 for four
// different quadrant values
if (y*y == ySquare)
result += 4;
}
return result;
}
// Driver code
public static void main(String arg[])
{
int r = 5;
System.out.println(countLattice(r));
}
}
// This code is contributed by Anant Agarwal.
# Python3 program to find
# countLattice points on a circle
import math
# Function to count Lattice
# points on a circle
def countLattice(r):
if (r <= 0):
return 0
# Initialize result as 4 for (r, 0), (-r. 0),
# (0, r) and (0, -r)
result = 4
# Check every value that can be potential x
for x in range(1, r):
# Find a potential y
ySquare = r*r - x*x
y = int(math.sqrt(ySquare))
# checking whether square root is an integer
# or not. Count increments by 4 for four
# different quadrant values
if (y*y == ySquare):
result += 4
return result
# Driver program
r = 5
print(countLattice(r))
# This code is contributed by
# Smitha Dinesh Semwal
// C# program to find countLattice
// points on a circle
using System;
class GFG {
// Function to count Lattice
// points on a circle
static int countLattice(int r)
{
if (r <= 0)
return 0;
// Initialize result as 4
// for (r, 0), (-r. 0),
// (0, r) and (0, -r)
int result = 4;
// Check every value that
// can be potential x
for (int x = 1; x < r; x++)
{
// Find a potential y
int ySquare = r*r - x*x;
int y = (int)Math.Sqrt(ySquare);
// checking whether square root
// is an integer or not. Count
// increments by 4 for four
// different quadrant values
if (y*y == ySquare)
result += 4;
}
return result;
}
// Driver code
public static void Main()
{
int r = 5;
Console.Write(countLattice(r));
}
}
// This code is contributed by nitin mittal.
<script>
// javascript program to find
// countLattice points on a circle
// Function to count
// Lattice points on a circle
function countLattice(r) {
if (r <= 0)
return 0;
// Initialize result as 4 for (r, 0), (-r. 0),
// (0, r) and (0, -r)
var result = 4;
// Check every value that can be potential x
for (x = 1; x < r; x++)
{
// Find a potential y
var ySquare = r * r - x * x;
var y = parseInt( Math.sqrt(ySquare));
// checking whether square root is an integer
// or not. Count increments by 4 for four
// different quadrant values
if (y * y == ySquare)
result += 4;
}
return result;
}
// Driver code
var r = 5;
document.write(countLattice(r));
// This code is contributed by umadevi9616
</script>
<?php
// PHP program to find countLattice
// points on a circle
// Function to count Lattice
// points on a circle
function countLattice($r)
{
if ($r <= 0)
return 0;
// Initialize result as 4
// for (r, 0), (-r. 0),
// (0, r) and (0, -r)
$result = 4;
// Check every value that
// can be potential x
for ($x = 1; $x < $r; $x++)
{
// Find a potential y
$ySquare = $r * $r - $x * $x;
$y = ceil(sqrt($ySquare));
// checking whether square
// root is an integer
// or not. Count increments
// by 4 for four different
// quadrant values
if ($y * $y == $ySquare)
$result += 4;
}
return $result;
}
// Driver Code
$r = 5;
echo countLattice($r);
// This code is contributed by nitin mittal
?>
Output:
12
Time Complexity: O(r), where “r” is the radius of the circle.
Auxiliary Space: O(1)
Reference:
http://mathworld.wolfram.com/CircleLatticePoints.html
Contact Us