PracHub
QuestionsPremiumCoachesLearningGuidesInterview Prep
|Home/Coding & Algorithms/Google

Find numbers with exactly two sum-of-squares forms

Last updated: Mar 29, 2026

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.

  • hard
  • Google
  • Coding & Algorithms
  • Software Engineer

Find numbers with exactly two sum-of-squares forms

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.

Related Interview Questions

  • Solve Rooms and Top-K Streams - Google (medium)
  • Find Containing Range - Google (medium)
  • Rearrange Tasks With Cooldown - Google (medium)
  • Implement Employee Management and Expression Evaluation - Google (medium)
  • Solve Three Array and Matrix Path Problems - Google (medium)
Google logo
Google
Oct 14, 2025, 12:00 AM
Software Engineer
Technical Screen
Coding & Algorithms
6
0
Loading...

Given an integer nnn, find all integers sss such that 0≤s<n0 \le s < n0≤s<n and sss can be expressed as a sum of two squares in exactly two distinct unordered ways:

s=a2+b2s = a^2 + b^2s=a2+b2

where aaa and bbb are non-negative integers, and (a,b)(a,b)(a,b) and (b,a)(b,a)(b,a) are considered the same representation (i.e., order does not matter).

Return all such sss (in any order, unless otherwise specified).

Example

  • For n>50n > 50n>50 , 505050 qualifies because:
    • 50=12+7250 = 1^2 + 7^250=12+72
    • 50=52+5250 = 5^2 + 5^250=52+52 and there are exactly two unordered representations.

Constraints

  • 1≤n<231−11 \le n < 2^{31}-11≤n<231−1

Notes

  • Representations must use non-negative integers.
  • Count unordered pairs: enforce a≤ba \le ba≤b to avoid double-counting.

Submit Your Answer to Earn 20XP

Sign in to leave a comment

Loading comments...

Browse More Questions

More Coding & Algorithms•More Google•More Software Engineer•Google Software Engineer•Google Coding & Algorithms•Software Engineer Coding & Algorithms
PracHub

Master your tech interviews with 8,000+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.