Katkat
Back

Find numbers with exactly two sum-of-squares forms

GoogleSoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests knowledge of the sum-of-two-squares theorem and efficient counting of integer partitions into two squares, requiring an understanding of number theory or optimization via circle/grid search.

Problem Statement

Given an integer N, find all positive integers x such that x <= N and x can be expressed as the sum of two squares of non-negative integers (a^2 + b^2 = x) in exactly two distinct ways. Two representations are considered the same if they differ only by the order of a and b (i.e., a^2 + b^2 is the same as b^2 + a^2).

Function Signature

def find_two_sum_squares(N: int) -> List[int]:

Constraints

  • 1 <= N <= 1,000,000

Examples

Example 1: Input: N = 50 Output: [50] Explanation:

  • 50 = 1^2 + 7^2 = 5^2 + 5^2. (Two ways)
  • 25 = 0^2 + 5^2 = 3^2 + 4^2. (Two ways)
  • Note: The output should be the list of integers meeting the criteria, sorted in ascending order.

Example 2: Input: N = 25 Output: [25]

Notes

  • Representations like (0, 5) and (3, 4) are distinct.
  • Ensure you handle cases where a or b might be zero.
  • Consider memory efficiency for the requested range of N.

Hints

Hint 1

You can precompute an array `count` of size N+1 where `count[i]` stores the number of pairs `(a, b)` such that `a <= b` and `a^2 + b^2 = i`.

Hint 2

Iterate through all possible values of `a` from 0 up to `sqrt(N)`, and for each `a`, iterate `b` from `a` up to `sqrt(N - a^2)`.

Hint 3

Since the maximum value of N is 1,000,000, an O(N) or O(N log N) approach is sufficient.

Follow-up questions

  • How would you modify your approach if N was 10^12, and you only needed to count the numbers rather than list them?
  • Can you derive the number of ways to express an integer as a sum of two squares using its prime factorization (Sum of Two Squares Theorem)?
  • What is the time complexity of your approach if we want to find all numbers up to N with exactly K representations?