Count Distinct Non-Negative Integer Pairs (x, y) that Satisfy the Inequality x*x + y*y < n - GeeksforGeeks
Given a positive number n, count all distinct Non-Negative Integer pairs (x, y) that satisfy the inequality x*x + y*y < n.
O(√n):The idea is to first find the count of all y values corresponding the 0 value of x. Let count of distinct y values be yCount. We can find yCount by running a loop and comparing yCount*yCount with n.
After we have initial yCount, we can one by one increase value of x and find the next value of yCount by reducing yCount.
In every step inside the inner loop, value of yCount is decremented by 1. The value yCount can decrement at most O(√n) times as yCount is count y values for x = 0. In the outer loop, the value of x is incremented. The value of x can also increment at most O(√n) times as the last x is for yCount equals to 1.
O(n): The outer loop runs √n times. The inner loop runs at most √n times.
TODO: check this answer:
http://ideone.com/BCIK5A
it's not a good idea to call sqrt in loop for this problem.
Java: Math.sqrt() => it calls native method.
Read full article from Count Distinct Non-Negative Integer Pairs (x, y) that Satisfy the Inequality x*x + y*y < n - GeeksforGeeks
Given a positive number n, count all distinct Non-Negative Integer pairs (x, y) that satisfy the inequality x*x + y*y < n.
O(√n):The idea is to first find the count of all y values corresponding the 0 value of x. Let count of distinct y values be yCount. We can find yCount by running a loop and comparing yCount*yCount with n.
After we have initial yCount, we can one by one increase value of x and find the next value of yCount by reducing yCount.
In every step inside the inner loop, value of yCount is decremented by 1. The value yCount can decrement at most O(√n) times as yCount is count y values for x = 0. In the outer loop, the value of x is incremented. The value of x can also increment at most O(√n) times as the last x is for yCount equals to 1.
// This function counts number of pairs (x, y) that satisfy
// the inequality x*x + y*y < n.
int
countSolutions(
int
n)
{
int
x = 0, yCount, res = 0;
// Find the count of different y values for x = 0.
for
(yCount = 0; yCount*yCount < n; yCount++) ;
// One by one increase value of x, and find yCount for
// current x. If yCount becomes 0, then we have reached
// maximum possible value of x.
while
(yCount != 0)
{
// Add yCount (count of different possible values of y
// for current x) to result
res += yCount;
// Increment x
x++;
// Update yCount for current x. Keep reducing yCount while
// the inequality is not satisfied.
while
(yCount != 0 && (x*x + (yCount-1)*(yCount-1) >= n))
yCount--;
}
return
res;
}
O(n): The outer loop runs √n times. The inner loop runs at most √n times.
int
countSolutions(
int
n)
{
int
res = 0;
for
(
int
x = 0; x*x < n; x++)
for
(
int
y = 0; x*x + y*y < n; y++)
res++;
return
res;
}
TODO: check this answer:
http://ideone.com/BCIK5A
it's not a good idea to call sqrt in loop for this problem.
Java: Math.sqrt() => it calls native method.
Read full article from Count Distinct Non-Negative Integer Pairs (x, y) that Satisfy the Inequality x*x + y*y < n - GeeksforGeeks