How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Google.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Google during technical interviews.

Find numbers with exactly two sum-of-squares forms

Q: Find numbers with exactly two sum-of-squares forms

This question evaluates understanding of integer representations as sums of two squares and the ability to reason about counting distinct unordered representations, drawing on elementary number theory and algorithmic enumeration.

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

Given an integer \(n\), find all integers \(s\) such that \(0 \le s < n\) and \(s\) can be expressed as a sum of two squares in **exactly two distinct unordered ways**: \[ s = a^2 + b^2 \] where \(a\) and \(b\) are **non-negative integers**, and \((a,b)\) and \((b,a)\) are considered the **same** representation (i.e., order does not matter). Return all such \(s\) (in any order, unless otherwise specified). ### Example - For \(n > 50\), \(50\) qualifies because: - \(50 = 1^2 + 7^2\) - \(50 = 5^2 + 5^2\) and there are exactly two unordered representations. ### Constraints - \(1 \le n < 2^{31}-1\) ### Notes - Representations must use **non-negative** integers. - Count unordered pairs: enforce \(a \le b\) to avoid double-counting.

Quick Answer: This question evaluates understanding of integer representations as sums of two squares and the ability to reason about counting distinct unordered representations, drawing on elementary number theory and algorithmic enumeration.

Given an integer `n`, find all integers `s` such that `0 <= s < n` and `s` can be expressed as a sum of two squares ``` s = a^2 + b^2 ``` in **exactly two distinct unordered ways**, where `a` and `b` are **non-negative** integers and `(a, b)` and `(b, a)` count as the **same** representation (enforce `a <= b` to avoid double-counting). Return the qualifying values in **ascending order**. ### Example `n = 51` -> `[25, 50]` - `25 = 0^2 + 5^2 = 3^2 + 4^2` - `50 = 1^2 + 7^2 = 5^2 + 5^2` Each has exactly two unordered representations, and both are `< 51`. ### Approach Enumerate every unordered pair `(a, b)` with `0 <= a <= b` whose squared sum is `< n`, tally how many representations each sum receives in a hash map, then return every sum whose count is exactly `2`. Bounding the loops by `a*a < n` and `a*a + b*b < n` keeps the work near `O(n)` pairs. ### Constraints - `1 <= n < 2^31 - 1` - Representations use non-negative integers; order does not matter.

Constraints

1 <= n < 2^31 - 1
a and b are non-negative integers
(a, b) and (b, a) are the same representation (enforce a <= b)
Return values in ascending order

Examples

Input: (51,)

Expected Output: [25, 50]

Explanation: 25 = 0^2+5^2 = 3^2+4^2 and 50 = 1^2+7^2 = 5^2+5^2; both have exactly two unordered forms and are < 51.

Input: (100,)

Expected Output: [25, 50, 65, 85]

Explanation: Adds 65 = 1^2+8^2 = 4^2+7^2 and 85 = 2^2+9^2 = 6^2+7^2, each with exactly two representations below 100.

Input: (66,)

Expected Output: [25, 50, 65]

Explanation: 65 now qualifies (65 < 66) but 85 does not, since 85 >= 66.

Input: (26,)

Expected Output: [25]

Explanation: The bound is exclusive: 25 < 26 is included, while 50 is excluded.

Input: (25,)

Expected Output: []

Explanation: 25 is not < 25, so no value in [0, 25) has exactly two representations.

Input: (2,)

Expected Output: []

Explanation: Only s in {0, 1} are in range; neither has two distinct sum-of-squares forms.

Input: (1,)

Expected Output: []

Explanation: Only s = 0 is in range, which has a single representation 0^2 + 0^2.

Input: (0,)

Expected Output: []

Explanation: Empty range; nothing to return.

Hints

Brute-forcing every value s and re-deriving its representations is wasteful. Instead, generate the representations once: iterate every unordered pair (a, b) with 0 <= a <= b and a^2 + b^2 < n, and tally each resulting sum in a hash map.
Bound the outer loop by a*a < n and the inner loop by a*a + b*b < n so you never exceed the range, and start b at a (not 0) so (a, b) and (b, a) are counted once.
After tallying, the answer is every sum whose count equals exactly 2. Sort before returning for a deterministic order.

Quick Overview

This question evaluates understanding of integer representations as sums of two squares and the ability to reason about counting distinct unordered representations, drawing on elementary number theory and algorithmic enumeration.