Problem

Given an integer N, find pairs of non-negative integers (x, y) such that:

1

N^2 = x^2 + y^2
  • Input: integer N (assume N >= 0).
  • Output: all integer pairs (x, y) with 0 <= x, y <= N satisfying the equation, or a count of such pairs depending on the API.

Examples

Example 1

1
2
3

Input: n = 5
Output: 2
Explanation: We can have following pairs, which match the criteria (0,5),(3,4),(4,3),(5,0), but only 2 are unique - (0,5),(3,4).

Example 2

1
2
3

Input: n = 1
Output: 1
Explanation: We can have following pairs, which match the criteria (0,1),(1), but only 1 is unique - (0,1).
Similar Problems

Solution

Method 1 — Brute force with integer sqrt

Intuition

For each x in 0..N compute rem = N*N - x*x. If rem is a perfect square y*y then (x,y) is a valid solution. To count unique unordered pairs (treat (x,y) same as (y,x)), only accept the solution when x <= y — this ensures each unordered pair is counted once. Use an integer square-root (isqrt) to avoid floating-point rounding issues.

Approach

  1. Compute target = N * N.
  2. For x from 0 to N:
  • Let rem = target - x*x.
  • Let y = isqrt(rem) (integer square root).
  • If y*y == rem and x <= y, record/count the unordered pair (x, y).

This guarantees we count each unordered pair once (for example, (3,4) will be found when x=3 but not again when x=4 because 4 <= 3 is false).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
 public:
  int countPairs(int n) {
    int N = n;
    int target = N * N;
    int ans = 0;
    for (int x = 0; x <= N; ++x) {
      int rem = target - x * x;
      if (rem < 0) break;
      int y = (int)std::floor(std::sqrt((double)rem));
      if (y * y == rem && x <= y) ++ans; // only count when x<=y to get unordered pairs
    }
    return ans;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

package main

import "math"

type Solution struct{}

func (s Solution) CountPairs(n int) int {
  N := n
  target := N * N
  ans := 0
  for x := 0; x <= N; x++ {
    rem := target - x*x
    if rem < 0 { break }
    y := int(math.Floor(math.Sqrt(float64(rem))))
    if y*y == rem && x <= y { ans++ }
  }
  return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
  public int countPairs(int n) {
    int N = n;
    int target = N * N;
    int ans = 0;
    for (int x = 0; x <= N; ++x) {
      int rem = target - x * x;
      if (rem < 0) break;
      int y = (int)Math.floor(Math.sqrt(rem));
      if (y * y == rem && x <= y) ++ans;
    }
    return ans;
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
  fun countPairs(n: Int): Int {
    val N = n
    val target = N * N
    var ans = 0
    var x = 0
    while (x <= N) {
      val rem = target - x * x
      if (rem < 0) break
      val y = Math.floor(Math.sqrt(rem.toDouble())).toInt()
      if (y * y == rem && x <= y) ans++
      x++
    }
    return ans
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
  def countPairs(self, n: int) -> int:
    import math
    target = n * n
    ans = 0
    for x in range(n + 1):
      rem = target - x * x
      if rem < 0:
        break
      y = math.isqrt(rem)
      if y * y == rem and x <= y:  # enforce x<=y to count unordered pairs once
        ans += 1
    return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

pub struct Solution;
impl Solution {
  pub fn countPairs(&self, n: i32) -> i32 {
    let N = n;
    let target = N * N;
    let mut ans: i32 = 0;
    for x in 0..=N {
      let rem = target - x * x;
      if rem < 0 { break; }
      let y = (rem as f64).sqrt().floor() as i32;
      if y * y == rem && x <= y { ans += 1; }
    }
    ans
  }
}

Complexity

  • ⏰ Time complexity: O(N) — loop over x from 0 to N, each iteration does an O(1) sqrt check.
  • 🧺 Space complexity: O(1) — constant extra space.

Method 2 — Two-pointer over squares

Intuition

Think of the sequence of squares 0^2, 1^2, …, N^2. Use two indices i (low) and j (high) starting at 0 and N. At any time the sum s = i*i + j*j moves monotonically as you shift pointers: increasing i increases s, decreasing j decreases s. This monotonicity lets you find all pairs in linear time without sqrt.

To count unique unordered pairs, maintain the invariant i <= j and only count a solution when i <= j is true (the loop condition enforces this). When a match is found, increment i and decrement j to skip the symmetric counterpart (j,i) and avoid double-counting. If i == j and i*i + j*j == target, that corresponds to a pair where both elements are equal (only possible when N^2 is twice a square) and should be counted once.

Approach

  1. Set i = 0, j = N, target = N*N, ans = 0.

  2. While i <= j:

  • Let s = i*i + j*j.
  • If s == target, count the unordered pair and do i++, j-- (this moves past the symmetric pair and preserves uniqueness).
  • Else if s < target, i++.
  • Else j--.
  1. Return ans.

This counts each unordered pair exactly once.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
 public:
  int countPairs(int N) {
    int ans = 0;
    int i = 0, j = N;
    int target = N * N;
    while (i <= j) {
      int s = i * i + j * j;
      if (s == target) { ++ans; ++i; --j; } // move both pointers to avoid double-count
      else if (s < target) ++i;
      else --j;
    }
    return ans; // counts unordered pairs with i <= j
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

package main

func (s Solution) CountPairs(N int) int {
  ans := 0
  i, j := 0, N
  target := N * N
  for i <= j {
    ssum := i*i + j*j
    if ssum == target { ans++; i++; j-- }
    else if ssum < target { i++ }
    else { j-- }
  }
  return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
  public int countPairs(int N) {
    int ans = 0;
    int i = 0, j = N;
    int target = N * N;
    while (i <= j) {
      int s = i * i + j * j;
      if (s == target) { ++ans; ++i; --j; }
      else if (s < target) ++i;
      else --j;
    }
    return ans;
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
  fun countPairs(N: Int): Int {
    var ans = 0
    var i = 0
    var j = N
    val target = N * N
    while (i <= j) {
      val s = i * i + j * j
      if (s == target) { ans++; i++; j-- }
      else if (s < target) i++
      else j--
    }
    return ans
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
  def countPairs(self, N: int) -> int:
    ans = 0
    i, j = 0, N
    target = N * N
    while i <= j:
      s = i * i + j * j
      if s == target:
        ans += 1
        i += 1
        j -= 1
      elif s < target:
        i += 1
      else:
        j -= 1
    return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

pub struct Solution;
impl Solution {
  pub fn countPairs(&self, N: i32) -> i32 {
    let mut ans: i32 = 0;
    let mut i: i32 = 0;
    let mut j: i32 = N;
    let target: i32 = N * N;
    while i <= j {
      let s = i * i + j * j;
      if s == target { ans += 1; i += 1; j -= 1; }
      else if s < target { i += 1; }
      else { j -= 1; }
    }
    ans
  }
}

Complexity

  • ⏰ Time complexity: O(N) — each pointer moves at most N steps; or the brute-force version performs N+1 iterations each with O(1) checks.
  • 🧺 Space complexity: O(1) — constant extra space.

Notes

  • Number-theory remark: an integer m is representable as sum of two squares iff every prime factor p ≡ 3 (mod 4) appears with an even exponent in m’s prime factorization. For m = N^2 this condition always holds, so representations exist; counting distinct representations requires Gaussian-integer factorization and is beyond this note’s scope.