Sum of Square Numbers Python Solution

Tested Python solution for LeetCode 633 with 21 pytest cases. Generate a practice environment with lcpy.

LeetCode 633, Medium. Topics: Math, Two Pointers, Binary Search. View on LeetCode.

Generate this problem as a practice environment: tested reference solution, 21 parametrized pytest cases, and a playground notebook:

lcpy gen -n 633   # by problem number
lcpy gen -s sum_of_square_numbers   # by problem name

​

Problem

Given a non-negative integer c, decide whether there’re two integers a and b such that a^2 + b^2 = c.

​

Examples

Input: c = 5
Output: true
Explanation: 1 * 1 + 2 * 2 = 5

Input: c = 3
Output: false

​

Constraints

• 0 <= c <= 2^31 - 1

​

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

from math import isqrt


class Solution:
    # Time: O(sqrt(c))
    # Space: O(1)
    def judge_square_sum(self, c: int) -> bool:
        left, right = 0, isqrt(c)
        while left <= right:
            total = left * left + right * right
            if total == c:
                return True
            if total < c:
                left += 1
            else:
                right -= 1
        return False

​

Complexity

Time	Space
O(sqrt(c))	O(1)

​

Tags

NeetCode All.