Given a positive number n, count all distinct Non-Negative Integer pairs (x, y) that satisfy the inequality x*x + y*y < n.
Examples:
Input: n = 5
Output: 6
The pairs are (0, 0), (0, 1), (1, 0), (1, 1), (2, 0), (0, 2)
Input: n = 6
Output: 8
The pairs are (0, 0), (0, 1), (1, 0), (1, 1), (2, 0), (0, 2),
(1, 2), (2, 1)
A Simple Solution is to run two loops. The outer loop goes for all possible values of x (from 0 to √n). The inner loops pick all possible values of y for the current value of x (picked by outer loop).
Following is the implementation of a simple solution.
C++
#include <iostream>using namespace std;// This function counts number of pairs (x, y) that satisfy// the inequality x*x + y*y < n.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;}// Driver program to test above functionint main(){ cout << "Total Number of distinct Non-Negative pairs is " << countSolutions(6) << endl; return 0;} |
Java
// Java code to Count Distinct // Non-Negative Integer Pairs // (x, y) that Satisfy the // inequality x*x + y*y < nimport java.io.*;class GFG { // This function counts number // of pairs (x, y) that satisfy // the inequality x*x + y*y < n. static 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; } // Driver program public static void main(String args[]) { System.out.println ( "Total Number of distinct Non-Negative pairs is " +countSolutions(6)); }}// This article is contributed by vt_m. |
Python3
# Python3 implementation of above approach# This function counts number of pairs # (x, y) that satisfy# the inequality x*x + y*y < n.def countSolutions(n): res = 0 x = 0 while(x * x < n): y = 0 while(x * x + y * y < n): res = res + 1 y = y + 1 x = x + 1 return res# Driver program to test above functionif __name__=='__main__': print("Total Number of distinct Non-Negative pairs is ", countSolutions(6))# This code is contributed by# Sanjit_Prasad |
C#
// C# code to Count Distinct // Non-Negative Integer Pairs // (x, y) that Satisfy the // inequality x*x + y*y < nusing System;class GFG { // This function counts number // of pairs (x, y) that satisfy // the inequality x*x + y*y < n. static 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; } // Driver program public static void Main() { Console.WriteLine( "Total Number of " + "distinct Non-Negative pairs is " + countSolutions(6)); }}// This code is contributed by Sam007. |
PHP
<?php// PHP program Count Distinct// Non-Negative Integer Pairs// (x, y) that Satisfy the // Inequality x*x + y*y < n// function counts number of // pairs (x, y) that satisfy// the inequality x*x + y*y < n.function countSolutions($n){ $res = 0; for($x = 0; $x * $x < $n; $x++) for($y = 0; $x * $x + $y * $y < $n; $y++) $res++; return $res;}// Driver Code{ echo "Total Number of distinct Non-Negative pairs is "; echo countSolutions(6) ; return 0;}// This code is contributed by nitin mittal.?> |
Javascript
<script>// This function counts number // of pairs (x, y) that satisfy// the inequality x*x + y*y < n.function countSolutions( n){ let res = 0; for (let x = 0; x*x < n; x++){ for (let y = 0; x*x + y*y < n; y++){ res++; } } return res;}// Driver program to test above functiondocument.write("Total Number of distinct Non-Negative pairs is "+countSolutions(6));</script> |
Output:
Total Number of distinct Non-Negative pairs is 8
An upper bound for the time complexity of the above solution is O(n). The outer loop runs √n times. The inner loop runs at most √n times.
Auxiliary Space: O(1)
Using an Efficient Solution, we can find the count in O(√n) time. The idea is to first find the count of all y values corresponding to 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 the initial yCount, we can one by one increase the value of x and find the next value of yCount by reducing yCount.
C++
// An efficient C program to find different (x, y) pairs that// satisfy x*x + y*y < n.#include <iostream>using namespace std;// 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;}// Driver program to test above functionint main(){ cout << "Total Number of distinct Non-Negative pairs is " << countSolutions(6) << endl; return 0;} |
Java
// An efficient Java program to // find different (x, y) pairs // that satisfy x*x + y*y < n.import java.io.*;class GFG { // This function counts number //of pairs (x, y) that satisfy // the inequality x*x + y*y < n. static 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 forcurrent 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; } // Driver program public static void main(String args[]) { System.out.println ( "Total Number of distinct Non-Negative pairs is " +countSolutions(6)) ; }}// This article is contributed by vt_m. |
Python3
# An efficient python program to# find different (x, y) pairs # that satisfy x*x + y*y < n.# This function counts number of# pairs (x, y) that satisfy the# inequality x*x + y*y < n.def countSolutions(n): x = 0 res = 0 yCount = 0 # Find the count of different # y values for x = 0. while(yCount * yCount < n): yCount = yCount + 1 # 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 = res + yCount # Increment x x = x + 1 # Update yCount for current # x. Keep reducing yCount # while the inequality is # not satisfied. while (yCount != 0 and (x * x + (yCount - 1) * (yCount - 1) >= n)): yCount = yCount - 1 return res# Driver program to test # above functionprint ("Total Number of distinct ", "Non-Negative pairs is " , countSolutions(6))# This code is contributed by Sam007. |
C#
// An efficient C# program to // find different (x, y) pairs // that satisfy x*x + y*y < n.using System;class GFG { // This function counts number //of pairs (x, y) that satisfy // the inequality x*x + y*y < n. static 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 forcurrent 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; } // Driver program public static void Main() { Console.WriteLine( "Total Number of " + "distinct Non-Negative pairs is " + countSolutions(6)) ; }}// This code is contributed by Sam007. |
PHP
<?php// An efficient C program to find different // (x, y) pairs that satisfy x*x + y*y < n.// This function counts number of pairs // (x, y) that satisfy the inequality // x*x + y*y < n.function countSolutions( $n){ $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 and ($x * $x + ($yCount-1) * ($yCount-1) >= $n)) $yCount--; } return $res;}// Driver program to test above functionecho "Total Number of distinct Non-Negative", "pairs is ", countSolutions(6) ,"\n";// This code is contributed by anuj_67.?> |
Javascript
<script> // An efficient Javascript program to // find different (x, y) pairs // that satisfy x*x + y*y < n. // This function counts number //of pairs (x, y) that satisfy // the inequality x*x + y*y < n. function countSolutions(n) { let 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 forcurrent 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; } document.write( "Total Number of " + "distinct Non-Negative pairs is " + countSolutions(6)) ;</script> |
Output:
Total Number of distinct Non-Negative pairs is 8
Time Complexity of the above solution seems more but if we take a closer look, we can see that it is O(√n). In every step inside the inner loop, the value of yCount is decremented by 1. The value yCount can decrement at most O(√n) times as yCount is counted 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 1.
Auxiliary Space: O(1)
This article is contributed by Sachin Gupta. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!